fn main() { input! { n: usize, s: bytes, } let mut parser = Parse { s: s, pos: 0 }; let tree = parser.exp(); // assert!(parser.pos == n); let ans = calc(tree); if ans.sign == 0 { println!("0"); return; } // println!("{:?}", ans.data); if ans.sign < 0 { print!("-"); } use util::*; let mut res = String::new(); for (i, a) in ans.data.iter().rev().enumerate() { use std::fmt::*; if i == 0 { write!(&mut res, "{}", *a).ok(); } else { write!(&mut res, "{:<06}", *a).ok(); } } println!("{}", res); } fn naive(node: Ref) -> BigInt { match *node { Node::Add(l, r, _) => naive(l).add(&naive(r)), Node::Sub(l, r, _) => naive(l).sub(&naive(r)), Node::Mul(l, r, _) => naive(l).mul(&naive(r)), Node::Val(v) => v, } } fn calc(mut node: Ref) -> BigInt { let mut op = vec![]; let mut seed = BigInt::new(0); loop { match *node { Node::Add(l, r, _) => { if l.size() >= r.size() { node = l; op.push((BigInt::new(1), calc(r))); } else { node = r; op.push((BigInt::new(1), calc(l))); } }, Node::Sub(l, r, _) => { if l.size() >= r.size() { node = l; op.push((BigInt::new(1), calc(r).neg())); } else { node = r; op.push((BigInt::new(1).neg(), calc(l))); } }, Node::Mul(l, r, _) => { if l.size() >= r.size() { node = l; op.push((calc(r), BigInt::new(0))); } else { node = r; op.push((calc(l), BigInt::new(0))); } }, Node::Val(v) => { seed = v; break; } } } let (a, b) = dfs(op); a.mul(&seed).add(&b) } fn dfs(mut a: Vec<(BigInt, BigInt)>) -> (BigInt, BigInt) { if a.is_empty() { return (BigInt::new(1), BigInt::new(0)); } if a.len() == 1 { return a[0].clone(); } let m = a.len() / 2; let b = a.split_off(m); let (x, y) = dfs(a); let (z, w) = dfs(b); (x.mul(&z), x.mul(&w).add(&y)) } struct Parse { s: Vec, pos: usize, } impl Parse { fn exp(&mut self) -> Ref { let mut l = self.term(); while self.peek().map_or(false, |c| c == b'+' || c == b'-') { let op = self.eat(); let r = self.term(); if op == b'+' { l = Box::new(Node::add(l, r)); } else { l = Box::new(Node::sub(l, r)); } } l } fn term(&mut self) -> Ref { let mut l = self.factor(); while self.peek().map_or(false, |c| c == b'*') { assert_eq!(self.eat(), b'*'); let r = self.term(); l = Box::new(Node::mul(l, r)); } l } fn factor(&mut self) -> Ref { if self.peek().unwrap() == b'(' { self.eat(); let v = self.exp(); assert_eq!(self.eat(), b')'); v } else { self.number() } } fn number(&mut self) -> Ref { let mut cnt = 0; while self.peek() == Some(b'-') { cnt += 1; self.eat(); } let mut s = vec![]; while self.peek().map_or(false, |c| b'0' <= c && c <= b'9') { s.push(self.eat()); } let mut val = BigInt::from_str(&s); if cnt % 2 == 1 { val.sign *= -1; } Box::new(Node::Val(val)) } fn peek(&self) -> Option { self.s.get(self.pos).cloned() } fn eat(&mut self) -> u8 { let v = self.s[self.pos]; self.pos += 1; v } } type Ref = Box; #[derive(Debug)] enum Node { Add(Ref, Ref, usize), Sub(Ref, Ref, usize), Mul(Ref, Ref, usize), Val(BigInt), } impl Node { fn size(&self) -> usize { match *self { Node::Add(_, _, s) => s, Node::Sub(_, _, s) => s, Node::Mul(_, _, s) => s, Node::Val(_) => 1, } } fn add(l: Ref, r: Ref) -> Self { let size = l.size() + r.size(); Node::Add(l, r, size) } fn sub(l: Ref, r: Ref) -> Self { let size = l.size() + r.size(); Node::Sub(l, r, size) } fn mul(l: Ref, r: Ref) -> Self { let size = l.size() + r.size(); Node::Mul(l, r, size) } } const BASE: u64 = 1_000_000; const L: usize = 6; #[derive(Clone, Debug)] struct BigInt { sign: i64, data: Vec, } impl BigInt { pub fn new(a: i64) -> Self { let sign = a.signum(); let mut a = (a * sign) as u64; let mut val = vec![]; while a > 0 { val.push(a % BASE); a /= BASE; } let mut res = Self { sign, data: val }; res.fix(); res } pub fn from_str(s: &[u8]) -> Self { let data = s .rchunks(L) .map(|s| s.iter().fold(0u64, |s, a| 10 * s + (*a - b'0') as u64)) .collect::>(); let mut res = Self { sign: 1, data: data, }; res.fix(); res } pub fn fix(&mut self) { while self.data.last().map_or(false, |p| *p == 0) { self.data.pop(); } if self.data.is_empty() { self.sign = 0; } } pub fn valid(&self) -> bool { if self.data.len() > 0 { self.data.last().map_or(false, |p| *p > 0) } else { self.sign == 0 } } pub fn neg(&self) -> Self { let mut v = self.clone(); v.sign *= -1; v } pub fn add(&self, rhs: &Self) -> Self { if self.sign == 0 { return rhs.clone(); } if rhs.sign == 0 { return self.clone(); } assert!(self.valid() && rhs.valid()); if self.sign == rhs.sign { let mut res = vec![0; self.data.len().max(rhs.data.len()) + 1]; let mut carry = 0; for (i, res) in res.iter_mut().enumerate() { let a = self.data.get(i).map_or(0, |p| *p); let b = rhs.data.get(i).map_or(0, |p| *p); let sum = a + b + carry; *res = sum % BASE; carry = sum / BASE; } assert!(carry == 0); let mut ans = Self { sign: self.sign, data: res, }; ans.fix(); ans } else { let large = if self.data.len() != rhs.data.len() { self.data.len() > rhs.data.len() } else { self.data .iter() .zip(rhs.data.iter()) .rev() .find(|p| *p.0 != *p.1) .map_or(true, |p| *p.0 > *p.1) }; let mut l = self; let mut r = rhs; if !large { std::mem::swap(&mut l, &mut r); } let mut carry = 0; let mut res = vec![0; l.data.len().max(r.data.len()) + 1]; for (i, res) in res.iter_mut().enumerate() { let a = l.data.get(i).map_or(0, |p| *p); let b = r.data.get(i).map_or(0, |p| *p); if a >= b + carry { *res = a - b - carry; carry = 0; } else { *res = a - b - carry + BASE; carry = 1; } } assert!(carry == 0); let mut ans = Self { sign: l.sign, data: res, }; ans.fix(); ans } } pub fn sub(&self, rhs: &Self) -> Self { self.add(&rhs.neg()) } pub fn mul(&self, rhs: &Self) -> Self { if self.sign == 0 || rhs.sign == 0 { return Self::new(0); } let mut data = karatsuba(&self.data, &rhs.data); let mut carry = 0; for i in 0.. { if carry == 0 && i >= data.len() { break; } if i >= data.len() { data.push(0); } let v = data[i] + carry; data[i] = v % BASE; carry = v / BASE; } Self { sign: self.sign * rhs.sign, data: data, } } } impl Zero for u64 { fn zero() -> Self { 0 } fn is_zero(&self) -> bool { *self == 0 } } impl One for u64 { fn one() -> Self { 1 } fn is_one(&self) -> bool { *self == 1 } } impl Ring for u64 {} use std::ops::*; pub trait Zero: Add + Sized { fn zero() -> Self; fn is_zero(&self) -> bool; } pub trait One: Mul + Sized { fn one() -> Self; fn is_one(&self) -> bool; } pub trait Ring: Zero + One + Sub {} pub trait Field: Ring + Div {} pub fn karatsuba(a: &[T], b: &[T]) -> Vec where T: Ring + Copy, { fn rec(a: &[T], b: &[T], c: &mut [T], buf: &mut [T]) where T: Ring + Copy, { if a.len() <= 16 { for (i, a) in a.iter().enumerate() { for (c, b) in c[i..].iter_mut().zip(b.iter()) { *c = *c + *a * *b; } } return; } let m = (a.len() + 1) / 2; let (la, ua) = a.split_at(m); let (lb, ub) = b.split_at(m); rec(la, lb, &mut c[..(2 * m)], buf); rec(ua, ub, &mut c[(2 * m)..], buf); let (x, buf) = buf.split_at_mut(m); let (y, buf) = buf.split_at_mut(m); let (z, buf) = buf.split_at_mut(2 * m); x.copy_from_slice(la); y.copy_from_slice(lb); let xa = x.iter_mut().zip(ua.iter()); let yb = y.iter_mut().zip(ub.iter()); for ((x, a), (y, b)) in xa.zip(yb) { *x = *x + *a; *y = *y + *b; } z.fill(T::zero()); rec(x, y, z, buf); for &s in [0, 2 * m].iter() { for (z, c) in z.iter_mut().zip(c[s..].iter()) { *z = *z - *c; } } for (c, z) in c[m..].iter_mut().zip(z.iter()) { *c = *c + *z; } } let need = a.len().min(b.len()); let mut buf = vec![T::zero(); 6 * need.next_power_of_two()]; let mut s = 0; let mut ans = vec![T::zero(); a.len() + b.len()]; let mut a = a; let mut b = b; while a.len() > 0 && b.len() > 0 { let len = a.len().min(b.len()); let (c, buf) = buf.split_at_mut(2 * len); c.fill(T::zero()); rec(&a[..len], &b[..len], c, buf); for (ans, c) in ans[s..].iter_mut().zip(c.iter()) { *ans = *ans + *c; } if a.len() == len { b = &b[len..]; } else { a = &a[len..]; } s += len; } ans.pop(); ans } // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 #[macro_export] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } #[macro_export] macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } #[macro_export] macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- mod util { pub trait Join { fn join(self, sep: &str) -> String; } impl Join for I where I: Iterator, T: std::fmt::Display, { fn join(self, sep: &str) -> String { let mut s = String::new(); use std::fmt::*; for (i, v) in self.enumerate() { if i > 0 { write!(&mut s, "{}", sep).ok(); } write!(&mut s, "{}", v).ok(); } s } } }