简答题
偏难
#7428
表达式求值 求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。 在计算机中,我们常用栈来解决这一问题。首先将中缀表达式转换到后缀表达式,然后对后缀表达式求…
表达式求值
求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。
在计算机中,我们常用栈来解决这一问题。首先将中缀表达式转换到后缀表达式,然后对后缀表达式求值。
加、减、乘、除、乘方分别用+,-,*, /, ^来表示。表达式可以有圆括号()。
时间限制: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 <bits/stdc++.h>
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<string> scaner(string s) // 字符串拆解放入vector
{
vector<string> ans;
string ops = "+-*/^()";
string t = "";
for (int i = 0; i < s.size(); i++) {
if (s[i] == '-' && (i + 1 < s.size()) && s[i + 1] >= '0' && s[i + 1] <= '9')
t = "-";
else if (s[i] >= '0' && s[i] <= '9')
t += s[i];
else if (ops.find(s[i]) != string::npos)
t += s[i];
else if (s[i] == ' ') {
if (t.size() > 0)
ans.push_back(t);
t = "";
}
}
if (t.size())
ans.push_back(t);
return ans;
}
vector<string> infix_Suffix(vector<string> exp) // 中缀表达式转后缀表达式
{
vector<string> ans;
stack<string> st;
string op = "+-*/^()";
for (int i = 0; i < 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() && get_fast(exp[i]) <= 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<string> exp) // 后缀表达式计算结果
{
stack<int> num;
string ops = "+-*/^";
for (int i = 0; i < 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 << num.top() << endl;
return num.top();
}
int main() {
string s;
getline(cin, s);
int n;
n = atoi(s.c_str());
while (n--) {
getline(cin, s);
vector<string> vs = scaner(s);
vs = infix_Suffix(vs);
suffix_calc(vs);
}
return 0;
}</pre>
这道题暂未补解析。