简答题 偏难
#7182

表达式求值 求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。 在计算机中,我们常用栈来解决这一问题。首先将中缀表达式转换到后缀表达式,然后对后缀表达式求…

表达式求值

求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。

在计算机中,我们常用栈来解决这一问题。首先将中缀表达式转换到后缀表达式,然后对后缀表达式求值。

加、减、乘、除、乘方分别用+,-,*, /, ^来表示。表达式可以有圆括号()。

时间限制:1000

内存限制:65536

输入

第一行为测试数据的组数N。 接下来的N行,每行是一个中缀表达式。 每个表达式中,圆括号、运算符和运算数相互之间都用空格分隔,运算数是整数。一般运算数可正可负(负数的符号和数字之间无空格),指数一定为自然数(0和正整数)。不必考虑除0的情况。每个运算数均可由int放下。不必考虑溢出。中缀表达式的字符串长度不超过600。乘方的优先级比乘除都高,结合性是向左结合,如2 ^ 3 ^ 4表示( 2 ^ 3 ) ^ 4 = 4096。除法的商向下取整。

输出

对每一组测试数据输出一行,为表达式的值

样例输入

2
31 * ( 5 - ( -3 + 25 ) ) + 70 ^ 2
2 * 5 + 6 * ( 7 - 8 ) + 6

样例输出

4373
10
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int get_fast(string op) // 运算符的优先级 {   int ans = -1;   switch (op[0]) {   case '+':   case '-':     ans = 1;     break;   case '*':   case '/':     ans = 2;     break;   case '^':     ans = 3;     break;   }   return ans; } vector&lt;string&gt; scaner(string s) // 字符串拆解放入vector {   vector&lt;string&gt; ans;   string ops = "+-*/^()";   string t = "";   for (int i = 0; i &lt; s.size(); i++) {     if (s[i] == '-' &amp;&amp; (i + 1 &lt; s.size()) &amp;&amp; s[i + 1] &gt;= '0' &amp;&amp; s[i + 1] &lt;= '9')       t = "-";     else if (s[i] &gt;= '0' &amp;&amp; s[i] &lt;= '9')       t += s[i];     else if (ops.find(s[i]) != string::npos)       t += s[i];     else if (s[i] == ' ') {       if (t.size() &gt; 0)         ans.push_back(t);       t = "";     }   }   if (t.size())     ans.push_back(t);   return ans; } vector&lt;string&gt; infix_Suffix(vector&lt;string&gt; exp) // 中缀表达式转后缀表达式 {   vector&lt;string&gt; ans;   stack&lt;string&gt; st;   string op = "+-*/^()";   for (int i = 0; i &lt; exp.size(); i++) {     if (exp[i] == "(")       st.push(exp[i]);     else if (exp[i] == ")") {       while (st.top() != "(") {         ans.push_back(st.top());         st.pop();       }       st.pop();     } else if (op.find(exp[i]) != string::npos) {       while (st.size() &amp;&amp; get_fast(exp[i]) &lt;= get_fast(st.top())) {         ans.push_back(st.top());         st.pop();       }       st.push(exp[i]);     } else       ans.push_back(exp[i]);   }   while (st.size()) {     ans.push_back(st.top());     st.pop();   }   return ans; } int suffix_calc(vector&lt;string&gt; exp) // 后缀表达式计算结果 {   stack&lt;int&gt; num;   string ops = "+-*/^";   for (int i = 0; i &lt; exp.size(); i++) {     if (ops.find(exp[i]) != string::npos) {       int a = num.top();       num.pop();       int b = num.top();       num.pop();       if (exp[i] == "+")         num.push(b + a);       else if (exp[i] == "-")         num.push(b - a);       else if (exp[i] == "*")         num.push(b * a);       else if (exp[i] == "/")         num.push(b / a);       else if (exp[i] == "^")         num.push(pow(b * 1.0, a));     } else       num.push(atoi(exp[i].c_str()));   }   cout &lt;&lt; num.top() &lt;&lt; endl;   return num.top(); } int main() {   string s;   getline(cin, s);   int n;   n = atoi(s.c_str());   while (n--) {     getline(cin, s);     vector&lt;string&gt; vs = scaner(s);     vs = infix_Suffix(vs);     suffix_calc(vs);   }   return 0; }</pre>
这道题暂未补解析。