题目链接
150. 逆波兰表达式求值
遍历所有元素。如果当前元素是整数,则压入栈;如果是运算符,则将栈顶两个元素弹出做相应运算,再将结果入栈。最终表达式扫描完后,栈里的数就是结果。
数组模拟栈
class Solution {
public:
int evalRPN(vector<string>& tokens) {
int stk[tokens.size()], tt = 0;
if(tokens.size() == 1) return stoi(tokens[0]);
for(auto &t : tokens)
if(t == "+" || t == "-" || t == "*" || t == "/"){
int a = stk[tt];
tt--;
int b = stk[tt];
tt--;
if(t == "+") stk[++tt] = a + b;
else if(t == "-") stk[++tt] = b - a;
else if(t == "*") stk[++tt] = b * a;
else stk[++tt] = b / a;
}
else stk[++tt] = stoi(t);
return stk[tt];
}
};
stack
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> sta;
for(auto &t : tokens)
if(t == "+" || t == "-" || t == "*" || t == "/"){
int a = sta.top();
sta.pop();
int b = sta.top();
sta.pop();
if(t == "+") sta.push(a + b);
else if(t == "-") sta.push(b - a);
else if(t == "*") sta.push(a * b);
else sta.push(b / a);
}
else sta.push(atoi(t.c_str()));
return sta.top();
}
};