Google+ Followers

Friday, December 6, 2013

[LeetCode] Evaluate Reverse Polish Notation, Solution

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


[Thoughts]

对于逆波兰式,一般都是用栈来处理,依次处理字符串,

如果是数值,则push到栈里面

如果是操作符,则从栈中pop出来两个元素,计算出值以后,再push到栈里面,

则最后栈里面剩下的元素即为所求。


[Code]

1:       int evalRPN(vector<string> &tokens) {   
2:            stack<int> operand;   
3:            for(int i =0; i< tokens.size(); i++)   
4:            {   
5:                 if ((tokens[i][0] == '-' && tokens[i].size()>1) //negative number  
6:                           || (tokens[i][0] >= '0' && tokens[i][0] <= '9')) //positive number  
7:                 {   
8:                      operand.push(atoi(tokens[i].c_str()));   
9:                      continue;  
10:                 }  
11:                 int op1 = operand.top();  
12:                 operand.pop();  
13:                 int op2 = operand.top();  
14:                 operand.pop();  
15:                 if(tokens[i] == "+") operand.push(op2+op1);  
16:                 if(tokens[i] == "-") operand.push(op2-op1);  
17:                 if(tokens[i] == "*") operand.push(op2*op1);  
18:                 if(tokens[i] == "/") operand.push(op2/op1);  
19:            }  
20:            return operand.top();  
21:       }  


Post a Comment