首页 > 代码库 > Evaluate Reverse Polish Notation (5)

Evaluate Reverse Polish Notation (5)

2024-07-31 16:26:22   211人阅读

 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
标签：
stack；
这个问题是个后缀表达式问题，用stack堆栈来解决最简单有效。遇到数就将其压入堆栈，遇到运算符号就从栈顶取出两个数字参与运算。但是，要注意一个问题，每次弹出的两个数，其正确的运算顺序应该是后弹出的数在前，先弹出的数在后。举例说明：
0 3 /
弹出的时候是3先弹出，0次之，本来是0/3,如果没有按照正确的顺序，就变成了3/0，程序就会因为出现严重错误而崩溃了！
感觉这个题目很简单，但是因为上述的问题搞了很久才弄好，在编程之前，一定要多思考再动手！
贴出代码：
 1 int istoken(string s){ 2     if(s.compare("+")==0) 3         return 1; 4     if(s.compare("-")==0) 5         return 2; 6     if(s.compare("*")==0) 7         return 3; 8     if(s.compare("/")==0) 9         return 4;10     return -1;11 }//不同的返回值对应不同的情况12 int transform(string s){13     return atoi(s.c_str());//将string转换为int14 }15 class Solution {16 public:17     int evalRPN(vector<string> &tokens) {18         int len=tokens.size();19         int i;20         stack<int>end;21         for(i=0;i<len;i++){22             if(istoken(tokens[i])==-1){//将数压入堆栈23                 end.push(transform(tokens[i]));24             }25             else{26                 int n1=end.top();27                 end.pop();28                 int n2=end.top();29                 end.pop();//这里n1，n2交换了顺序30                 switch(istoken(tokens[i])){31                 case 1:{n1+=n2;break;}32                 case 2:{n1-=n2;break;}33                 case 3:{n1*=n2;break;}34                 case 4:{n1/=n2;break;}35                 }36                 end.push(n1);37             }38 39         }40         return end.top();41     }42 };

 

Evaluate Reverse Polish Notation (5)


联系
我们