中缀表达式转逆波兰表达式

需要数据结构栈——ops

遍历中缀表达式；

  • 若为数字：则直接输出到队列
  • 若为(：直接输出至队列
  • 若为)：将栈中的op输出至队列，直到栈顶字符为(
  • 若为+-*/：判断当前操作符和栈顶操作符之间的优先级
    • 若当前操作符>栈顶操作符
      • 直接入栈
    • 当前操作符<=栈顶操作符
      • 直接出栈
      • 继续判断优先级直到满足当前操作符>栈顶操作符
      • 将当前操作符入栈

        逆波兰表达式计算

        需要数据结构栈——nums，用于存储操作数。

遍历逆波兰表达式：

  • 若为数字直接入栈
  • 若为操作符op
    • int rval=nums.top();
    • nums.pop();
    • nums.top()+=nums.pop();

直接输出计算后的栈顶元素nums.top()。

中缀表达式转逆波兰计算时，顺便计算

当操作符栈ops出栈时，更新数字栈的栈顶！！ 便可顺便进行计算

  1. class Solution {
  2.     //优先级列表
  3.     unordered_map<char,int> priority={
  4.         {'(',0},
  5.         {'+',1},
  6.         {'-',1},
  7.         {'*',2},
  8.         {'/',2},
  9.     };
  10.     void ignore_whitespace(const char* &p){
  11.         while(*p==' ')
  12.             ++p;
  13.     }
  14.     inline bool is_op(char ch){
  15.         return ch == '+' || ch == '-'
  16.                 || ch == '*' || ch == '/';
  17.     }
  18.     //转换为int
  19.     int to_int(const char* &p){
  20.         ignore_whitespace(p);
  21.         assert(isdigit(*p));
  22.         int ret=0;
  23.         while(isdigit(*p)){
  24.             ret=ret*10+static_cast<int>(*p-'0');
  25.             ++p;
  26.         }
  27.         ignore_whitespace(p);
  28.         return ret;
  29.     }
  30.     //根据操作符和数字栈，更新数字栈
  31.     void _calcu(stack<int>& nums,stack<char>& ops){
  32.         int rval=nums.top();nums.pop();
  33.         char op=ops.top();
  34.         ops.pop();
  35.         switch(op){
  36.             case '+':
  37.                 nums.top()+=rval;
  38.                 break;
  39.             case '-':
  40.                 nums.top()-=rval;
  41.                 break;
  42.             case '*':
  43.                 nums.top()*=rval;
  44.                 break;
  45.             case '/':
  46.                 nums.top()/=rval;
  47.                 break;
  48.         }      
  49.     }
  51.     int convert_to_reverse_poland(string& s){
  52.         auto p=s.c_str();
  53.         stack<int> nums;
  54.         stack<char> ops;
  55.         while(*p!='\0'){
  56.             ignore_whitespace(p);
  57.             if(isdigit(*p)){
  58.                 nums.push(to_int(p));
  59.             }else if(*p=='('){
  60.                 ops.push(*p);
  61.                 ++p;
  62.             }else if(*p==')'){
  63.                 ++p;
  64.                 while(!ops.empty() && ops.top()!='('){
  65.                     _calcu(nums,ops);
  66.                 }
  67.                 ops.pop();  //！！！！  删除'('
  68.             }else{
  69.                 // + - * /
  70.                 char op=*p;
  71.                 ++p;
  72.                 while(!ops.empty() && priority[op]<=priority[ops.top()]){
  73.                     _calcu(nums,ops);
  74.                 }
  75.                 ops.push(op);
  76.             }
  77.         }
  78.         while(!ops.empty()){
  79.             _calcu(nums,ops);
  80.         }
  81.         return nums.top();
  82.     }
  84. public:
  85.     int calculate(string s) {
  86.         return convert_to_reverse_poland(s); 
  87.     }
  88. };