[LEETCODE]Evaluate Reverse Polish Notation

[LEETCODE] Evaluate Reverse Polish Notation

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

思路：

不是运算符的时候入栈，遇到运算符的时候出栈两个数字，计算新的值然后再入栈。

注意点：

1. string to integer 的处理， 使用函数 stoi();

2. 最后的结果是栈的最上面一个数。

3. 注意先出栈的是算式右边的数字，后出栈的是左边的，搞错了的话运算除法分母为0就错了

代码：

int evalRPN(vector<string> &tokens) {
 int len = tokens.size();
 int i = 0;
 int result;
 vector<int> stack;
 while(i<len){
  if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/"){
   int integer = stoi(tokens[i]);
   stack.push_back(integer);
  }
  else{
   int b = stack.back();
   stack.pop_back();
   int a = stack.back();
   stack.pop_back();
   if(tokens[i] == "+"){
    result = a+b;
   }
   else if(tokens[i] == "-"){
    result = a-b;
   }
   else if(tokens[i] == "*"){
    result = a*b;
   }
   else{
    result = a/b;
   }
   stack.push_back(result);
  }
  i++;
 }
 result = stack.back();
 return result;
}