搬砖
来自@Hasity的思路
“表达式求值”问题,两个核心关键点:
1.
双栈,一个操作数栈,一个运算符栈;
2.
运算符优先级,栈顶运算符 和 即将入栈的运算符的优先级比较:
如果栈顶的运算符优先级低,新运算符直接入栈如果栈顶的运算符优先级高,先出栈计算,新运算符再入栈
这个方法的时间复杂度为O(n),整个字符串只需要扫描一遍。
运算符有+=*/()^~&情况扩展即可
来自@acm_wf的代码注释
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
stack<int> num;//存储运算数
stack<char> op;//存储运算符
//模拟一次算术操作
void eval()
{
auto b = num.top(); num.pop();
auto a = num.top(); num.pop();
auto c = op.top(); op.pop();
int x;
if (c == '+') x = a + b;
else if (c == '-') x = a - b;
else if (c == '*') x = a * b;
else x = a / b;
num.push(x);
}
int main()
{
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
//建立映射来判断运算优先级,可以扩展
string str;
cin >> str;
for (int i = 0; i < str.size(); i ++ )
{
auto c = str[i];
if (isdigit(c))//读入运算数,从左往右一个一个读,读到非数字停止
{
int x = 0, j = i;
while (j < str.size() && isdigit(str[j]))
x = x * 10 + str[j ++ ] - '0';//j++ 迭代不能忘
i = j - 1;//由于每轮循环有i++,我们需要倒指向最后一个数字
num.push(x);
}
else if (c == '(') op.push(c); //标记一下,括号内数据
else if (c == ')')//读到右括号,先算括号
{
while (op.top() != '(') eval();//从右往左计算括号里的值
op.pop();//左括号可以弹出
}
else
{
//得先把乘除法算了再算加减
//这里必须得带等于号 我们这题都是正整数计算
// 0 - 5 + 3
//如果不算,上式会被错误计算成 -8
while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
op.push(c);//压入新运算符
}
}
while (op.size()) eval(); //清理低优先级操作
cout << num.top() << endl;
return 0;
}