题目:
Evaluate the value of an arithmetic expression in .
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
理解这道题首先要理解什么是波兰表达式、什么是逆波兰表达式,这个表达式的意义何在:看参考链接;
参考链接:
Evaluate Reverse Polish Notation:
波兰式、逆波兰式与表达式求值:
思路:遍历这个逆波兰表达式数组,遇到操作数推进操作数的栈s,遇到操作符,将栈s顶两个操作数a和b取出进行操作符运算,将运算结果c放进栈中。
1 class Solution { 2 public: 3 int evalRPN(vector&s) { 4 stack store; 5 for(auto x: s) 6 { 7 if(x=="+"||x=="-"||x=="*"||x=="/") 8 { 9 if(store.size()<2) return 0;10 int a=store.top();store.pop();11 int b=store.top();store.pop();12 int c=0;13 if(x=="+")14 c=a+b;15 else if(x=="-")16 c=b-a;17 else if(x=="*")18 c=b*a;19 else if(x=="/")20 c=b/a;21 store.push(c);22 }23 else24 {25 store.push(atoi(x.c_str()));26 }27 28 29 }30 return store.top();31 }32 };