Reverse Polish Notation

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> nums;
        int n = tokens.size();
        string s;
        for ( int i = 0; i <= n-1; i++ ) {
            s= tokens[i];
            if ( s != "+" and s != "-" and s != "*" and s != "/" ) nums.push(atoi(s.c_str()));
            else {
                int n1 = nums.top(); nums.pop();
                int n2 = nums.top(); nums.pop();
                if ( s == "+" ) nums.push(n1+n2);
                if ( s == "-" ) nums.push(n2-n1);
                if ( s == "*" ) nums.push(n1*n2);
                if ( s == "/" ) nums.push(n2/n1);
            }
        }
        return nums.top();
    }
};

Notes
The solution is pretty easy. But let's think about how to convert a normal "infix" notation to the reverse polish notation in "postfix" form.
When meet a

• number, print it...
• "(": push it to the stack
• "+" or "-":
  • print the top of the stack and pop it;
  • push it to stack
• "*" or "/": push it to stack
• ")":
  • print the top of the stack and pop it until meet "(". And then pop "(".

Note that in the "infix" expression: the operator is between the two operands. So we always have to examine the operator in a "reverse" way.
That's why we compare the "current" operator curr with the one on the top of the stack last. If the priority of last is higher or equal to curr, print and pop out the last. Otherwise, push in curr.

def postfix(s):
  s = '(' + s + ')'
  n = len(s)
  operator = []
  signs = ['+', '-', '*', '/', '(', ')']
  res = []
  tmp = ""
  for i in range(n):
    if ( s[i] == ' ' ): continue
    if ( s[i] not in signs ):
      tmp += s[i]
      continue
    if ( tmp != "" ):
      res.append(tmp)
      tmp = ""
    if ( s[i] == '(' ):
      operator.append(s[i])
      continue
    if ( s[i] == ')' ):
      while ( operator[-1] != '(' ):
        res.append(operator[-1])
        operator.pop(-1)
      operator.pop(-1)
      continue
    if ( len(operator) == 0 or operator[-1] == '(' ):
      operator.append(s[i])
      continue
    if ( len(operator) != 0 ):
      if ( s[i] == '*' or s[i] == '/' ):
        operator.append(s[i])
        continue
      if ( s[i] == '+' or s[i] == '-' ):
        res.append(operator[-1])
        operator.pop(-1)
        operator.append(s[i])
        continue
  return res

想研究这个问题是为了解决面经里“除去多余括号”的问题。网上看到一个思路：先转化成逆波兰式（Reverse Polish Notation），再转换成正常形式，（代码如下）这样就避免了不必要的括号。不知道有没有更好的解法？

def infix(s):
  n = len(s)
  signs = ['+', '-', '*', '/']
  number = []
  for i in range(n):
    if ( s[i] not in signs ):
      number.append([s[i], ''])
      continue
    n2, s2 = number[-1][0], number[-1][1]
    number.pop(-1)
    n1, s1 = number[-1][0], number[-1][1]
    number.pop(-1)
    if ( (s1 == '+' or s1 == '-') and (s[i] == '*' or s[i] == '/') ): n1 = '(' + n1 + ')'
    if ( (s2 == '+' or s2 == '-') and s[i] != '+'): n2 = '(' + n2 + ')'
    if ( (s2 == '*' or s2 == '/') and s[i] == '/'): n2 = '(' + n2 + ')'
    new = n1 + s[i] + n2
    number.append([new, s[i]])
  return number[0][0]