首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#7485

中缀表达式的值(2023.12) 人们熟悉的四则运算表达式称为中缀表达式,例如(23+34*45/(5+6+7))。在程序设计语言中,可以利用堆栈的方法把中缀表…

中缀表达式的值(2023.12)

人们熟悉的四则运算表达式称为中缀表达式,例如(23+34*45/(5+6+7))。在程序设计语言中,可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式(又称逆波兰表示法),并最终变为计算机可以直接执行的指令,得到表达式的值。 给定一个中缀表达式,编写程序,利用堆栈的方法,计算表达式的值。

时间限制:200

内存限制:65536

输入

第一行为测试数据的组数N 接下来的N行,每行是一个中缀表达式。表达式中只含数字、四则运算符和圆括号,操作数都是正整数,数和运算符、括号之间没有空格。中缀表达式的字符串长度不超过600。

输出

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


样例输入

3
3+5*8
(3+5)*8
(23+34*45/(5+6+7))

样例输出

43
64
108


提示

注意:运算过程均为整数运算(除法运算'/'即按照C++定义的int除以int的结果,测试数据不会出现除数为0的情况),输出结果也为整数(可能为负)。 中间计算结果可能为负。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<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] &gt;= '0' &amp;&amp; s[i] &lt;= '9')       t += s[i];     else if (ops.find(s[i]) != string::npos) {       if (t.size() &gt; 0)         ans.push_back(t);       t = s[i];       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;   int n;   cin &gt;&gt; n;   while (n--) {     cin &gt;&gt; s;     vector&lt;string&gt; vs = scaner(s);     vs = infix_Suffix(vs);     suffix_calc(vs);   }   return 0; }</pre>
这道题暂未补解析。