表达式求值-中缀转前缀表达式

时间限制：500ms 内存限制：256.0MB

　　 给定一个只包含加（\(+\)）、减（\(-\)）、乘（\(*\)）三种运算的\(n\)个字符的合法表达式，请求出该表达式的值对\(2527\)取余后的结果。

　　 第二行输入一个字符串\(S\)，表示一个合法表达式。

　　 输出一个整数，表示该表达式的值对\(2527\)取余后的结果。

　　 \(1\leq |S|\leq 5×10^6\)，其中\(|S|\)为字符串\(S\)的长度。

　　 保证表达式仅包含数字、左右括号、加号、减号、乘号，且表达式中的数字均为整数且\(\in [0, 2527)\)。

　　 请使用较快的读入方式。

　　 可以利用中缀表达式转后缀表达式的方法在计算。转化过程可以运用栈。

转化：

　　 \(s1[top]\) 用字符串模拟出栈的效果，方便存储后缀表达式，\(top\)为栈顶。

　　 \(s2\) 用于临时存贮运算符。

　　 \(str\) 用于存储中缀表达式。

　　 按顺序依次遍历\(str_i(0\leq i\leq len)\)。若为操作数，则直接入栈\(s1\)；若为左括号\((\)，则直接入栈\(s2\)；若为右括号\(')'\)，则栈\(s2\)将左括号\((\)以上的所有运算符一次出栈并入栈\(s1\)；若为运算符，则当栈\(s2\)栈顶元素为括号或者栈顶元素运算优先级比\(str_i\)低时或者栈为空时直接入栈，否则依次出栈并入栈到\(s1\)中，直到栈顶元素满足要求为止，再将\(str_i\)入栈\(s2\)。

　　 最终将栈\(s2\)中剩余元素依次出栈并入栈到\(s1\)中。

　　 得出后缀表达式。

求值：

　　 \(st\) \(int\)类型栈，用于存储操作数。

　　 按顺序依次遍历栈\(s1_i(0\leq i\leq len)\)。若\(isdigit(s1_i)\)，则找到\(j\)并满足\(!isdigit(s1_{j+1})\)，将操作数记下并压入栈\(st\)中；若为运算符，则将栈\(st\)弹出两个数并作出相应的运算，再将结果压入栈\(st\)中。

　　 栈\(st\)的栈顶元素即为该表达式的运算值。

-end-