-
首先给每个变量都开一个stack,用来记录当前的值
-
然后再开四个stack
-
var记录运算符和还未复制的变量
-
op记录当前仍在处理的运算符
-
num记录还没处理的数字
-
s记录的东西和var一样,用于退栈
-
遇到数字,如果有没有赋值的变量(说明当前op.top()=="let"),则进行赋值,更新这个变量的栈,否则说明是参与运算(add或mult)的,加入num中
-
如果遇到的是运算符直接加入
-
如果遇到变量,需要考虑的有两点
- 前面运算符是add或mult,那么直接将这个变量替换成数值,并加入num即可,无需其他操作
- 如果前面的是let,那么仍然要分两种情况,一种是在赋值运算符的左边,一种是在赋值运算符的右边
- 如果当前var栈顶是变量,那么就是作为赋值运算符的右边给左边赋值,直接给对应的变量赋值即可,无需其他操作
- 否则,如果右边是')',说明是let表达式最后一个,那么直接将该变量的值,push进num中,否则应当加入var中
-
当我们遇到')'
- 如果是add或者mult,那么从num中取出最后两个数计算
- 如果是let,那么就是num中最后一个数
- 然后利用s进行一个退栈的处理
- 然后我们将当前这个处理好的运算符退栈,然后看这个新的结果能不能赋值给前面的变量
class Solution {
public:bool check(string s) { return s == "add" || s == "mult" || s == "let"; }int evaluate(string expression) {unordered_map<string, stack<int>> val;stack<string> var, op, s;stack<int> num;int now = 0, sign = 1, j;string& str = expression;for (int i = 0; i < str.length(); ++i) {if (str[i] == ' ' || str[i] == '(')continue;if (str[i] == '-')sign = -1;else if (isdigit(str[i])) {now = str[i] - '0';j = i;while (j + 1 < str.length() && isdigit(str[j + 1])) {now = now * 10 - '0' + str[++j];}i = j;now *= sign;sign = 1;if (!check(var.top())) {val[var.top()].push(now);var.pop();} else {num.push(now);}} else if (str[i] == ')') {int x, y, z;if (op.top() == "add" || op.top() == "mult") {x = num.top();num.pop();y = num.top();num.pop();if (op.top() == "add")z = x + y;elsez = x * y;} else {z = num.top();num.pop();}var.pop();while (s.top() != op.top()) {val[s.top()].pop();s.pop();}s.pop();if (!var.empty() && !check(var.top())) {val[var.top()].push(z);var.pop();} elsenum.push(z);op.pop();} else {string t = "";t += str[i];j = i;while (j + 1 < str.length() && str[j + 1] != ' ' &&str[j + 1] != ')') {t += str[++j];}i = j;if (check(t)) {s.push(t);op.push(t);var.push(t);} else {if (op.top() == "add" || op.top() == "mult") {num.push(val[t].top());} else {if (!check(var.top())) {val[var.top()].push(val[t].top());var.pop();} else {if (str[j + 1] != ')') {var.push(t);s.push(t);} else {num.push(val[t].top());}}}}}}return num.top();}
};