逆波兰表达式求值

逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式。
逆波兰表达式求值的过程是：

  1. 如果遇到操作数，则将操作数入栈；
  2. 如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。

  1. // 逆波兰表达式求值，不带括号
  2. class Solution {
  3. public:
  4.     int evalRPN(vector<string>& tokens) 
  5.     {
  6.         stack<int> st;
  7.         for (auto& token : tokens) {
  8.             if (isNumber(token)) {
  9.                 st.push(stoi(token));
  10.             } else {
  11.                 int num2 = st.top();
  12.                 st.pop();
  13.                 int num1 = st.top();
  14.                 st.pop();
  15.                 switch (token[0]) {
  16.                     case '+':
  17.                         st.push(num1 + num2);
  18.                         break;
  19.                     case '-':
  20.                         st.push(num1 - num2);
  21.                         break;
  22.                     case '*':
  23.                         st.push(num1 * num2);
  24.                         break;
  25.                     case '/':
  26.                         st.push(num1 / num2);
  27.                         break;
  28.                 }
  29.             }
  30.         }
  31.         return st.top();
  32.     }
  34.     bool isNumber(string& token) 
  35.     {
  36.         if (token == "+" || token == "-" || token == "*" || token == "/") {
  37.             return false;
  38.         }
  39.         return true;
  40.     }
  41. };

中缀表达式转化为后缀表达式（逆波兰表达式）