题目描述
Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are+,-,,/. Each operand may be an integer or another expression.*
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
分析
引用辅助堆栈，采用堆栈进行将int和运算符分别压栈存储
代码
class Solution {
public:
int evalRPN(vector<string> &tokens) {
//建立int数字堆栈
stack<int>Stk;
int a = 0,b=0,c=0;
for(auto temp:tokens)
{
//判断是否为字符
if(temp == "+"||temp == "-"||temp=="*"||temp == "/")
{
//int堆栈存储数小于2
if(Stk.size()<2)
return 0;
a = Stk.top();Stk.pop();
b = Stk.top();Stk.pop();
switch(transform(temp))
{
case '+':c = a + b;break;
case '-':c = b - a;break;
case '*':c = b * a;break;
case '/':c = b / a;break;
}
Stk.push(c);
}
//如果为数字，压栈
else
{
Stk.push(atoi(temp.c_str()));
}
}
return Stk.top();
}
private:
//字符串hash到字符
char transform(string s){
char temp;
if(s=="+")
temp = '+';
else if(s=="-")
temp = '-';
else if(s=="*")
temp = '*';
else if(s=="/")
temp = '/';
return temp;
}
};
总结
合理引用辅助内存，栈。 stack是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶。
