【队列栈】逆波兰表达式

小鱼儿 2022-12-02 15:24 333阅读 0赞

##  ##

> 逆波兰表达式(Reverse Polish Notation)，一种不需要括号的后缀表达式。后缀表达式的所有运算符都在数字之后出现。

E.g.  
中缀表示式：9 + (3 - 1) \* 3 + 10 / 2  
后缀表达式：9 3 1 - 3 \* +10 2 / +

**将中缀表示式转为后缀表达式：**  
从左到右遍历中缀表达式中的运算符和数字，如果是数字直接输出作为后缀表达式的一部分。如果是运算符，则判断其与栈顶元素的优先级，是右括号或者优先级小于栈顶元素的，则栈中元素依次出栈（到左括号结束），并将当前运算符压入栈；如果优先级大于等于栈顶元素，直接入栈。

**后缀表示式求值：**  
从左到右遍历后缀表达式中的运算符和数字，遇到数字就进栈，遇到符号则弹出栈顶的两个元素进行运算，将结果压栈。

#include <iostream>
    #include <string>
    #include <stack>
    
    bool IsDigit(char c) { 
      return c >= '0' && c <= '9';
    }
    
    bool IsOperator(char c) { 
      return c == '+' || c == '-' || c == '/' || c == '*' || c == '(' || c == ')';
    }
    
    int GetPriority(char c) { 
      switch (c) { 
      case '+':
        return 1;
      case '-':
        return 1;
      case '*':
        return 2;
      case '/':
        return 2;
      default:
        return 0;
      }
    }
    
    std::string GetReversePolishStr(const std::string& str) { 
      std::string reverse_polish_str;
      std::stack<char> operator_stack;
      for (auto c : str) { 
        if (IsDigit(c)) { 
          reverse_polish_str.push_back(c);
          continue;
        }
        
        if (!IsOperator(c)) { 
          continue;
        }
        
        if (operator_stack.empty()) { 
          operator_stack.push(c);
          continue;
        }
        
        if (c == '(') { 
          operator_stack.push(c);
          continue;
        }
        
        // 遇到右括号，把左括号之后的运算符全部弹出。
        if (c == ')') { 
          while (operator_stack.top() != '(') { 
            reverse_polish_str.push_back(operator_stack.top());
            operator_stack.pop();
          }
          operator_stack.pop();
          continue;
        }
        
        char top = operator_stack.top();
        if (top == '(') { 
          operator_stack.push(c);
          continue;
        }
        
        if (GetPriority(top) <= GetPriority(c)) { 
          operator_stack.push(c);
          continue;
        }
        
        // 当栈顶元素优先级大于新的运算符，则全部弹出。
        while (!operator_stack.empty() && operator_stack.top() != '(') { 
          reverse_polish_str.push_back(operator_stack.top());
          operator_stack.pop();
        }
        operator_stack.push(c);
      }
      
      // 将栈里面的运算符全部弹出。
      while (!operator_stack.empty()) { 
        reverse_polish_str.push_back(operator_stack.top());
        operator_stack.pop();
      }
      return reverse_polish_str;
    }
    
    int Operate(int d1, int d2, char op) { 
      switch (op) { 
      case '*':
        return d1 * d2;
      case '/':
        return d2 / d1;
      case '+':
        return d1 + d2;
      case '-':
        return d2 - d1;
      default:
        return 0;
      }
    }
    
    int Calculate(const std::string& reverse_polish_str) { 
      std::stack<int> digit_stack;
      for (auto c : reverse_polish_str) { 
        if (IsDigit(c)) { 
          digit_stack.push(c - '0');
          continue;
        }
        
        int d1 = digit_stack.top();
        digit_stack.pop();
        int d2 = digit_stack.top();
        digit_stack.pop();
        digit_stack.push(Operate(d1, d2, c));
      }
      
      return digit_stack.top();
    }
    
    int main() { 
      std::string str;
      std::getline(std::cin, str);
      std::cout << str << std::endl;
      std::string reverse_polish_str = GetReversePolishStr(str);
      std::cout << reverse_polish_str << std::endl;
      std::cout << Calculate(reverse_polish_str) << std::endl;
      return 0;
    }