中缀表达式转后缀表达式的方法

    1. 如果遇到操作数，将其添加到后缀表达式的后面；
    2. 如果遇到操作符：
    • 操作符栈为空时，操作符入栈；
    • 遇到左括号时，左括号入栈（无论操作符栈是否为空）；
    • 遇到右括号时，依次弹出栈中的操作符（添加到后缀表达式中的后面），直到遇到左括号（弹出左括号），左右括号均不添加到后缀表达式中；
    • 遇到其他运算符时，依次弹出栈中优先级高于或等于当前操作符高的操作符（添加到后缀表达式后面），或者遇到左括号时停止，然后将当前操作符入栈；
    1. 将操作符栈中的元素依次弹出（添加到后缀表达式中的后面）。

    优先级可视为：* />+ ->(

    示例：
    中缀表达式1-2*3+(4*(5-6)+7)/8+9 转变为后缀表达式1 2 3 * - 4 5 6 - * 7 + 8 / + 9 +

    1. 初始状态
    • 操作符栈为[]，后缀表达式为""
    1. 遇到操作数1，添加到后缀表达式中
    • 操作符栈为[]，后缀表达式为"1"
    1. 遇到操作符-，此时操作符栈为空，直接入栈
    • 操作符栈为[-]，后缀表达式为"1"
    1. 遇到操作数2，添加到后缀表达式中
    • 操作符栈为[-]，后缀表达式为"1 2"
    1. 遇到操作符*，栈中无比*优先级高或相同的操作符，无需弹出，最后将该操作符入栈
    • 操作符栈为[- *]，后缀表达式为"1 2"
    1. 遇到操作数3，添加到后缀表达式中
    • 操作符栈为[- *]，后缀表达式为"1 2 3"
    1. 遇到操作符+，弹出栈中比+优先级高或相同的操作符* -添加到后缀表达式中，最后+入栈
    • 操作符栈为[+]，后缀表达式为"1 2 3 * -"
    1. 遇到左括号(，入栈
    • 操作符栈为[+ (]，后缀表达式为"1 2 3 * -"
    1. 遇到操作数4，追加到后缀表达式中
    • 操作符栈为[+ (]，后缀表达式为"1 2 3 * - 4"
    1. 遇到操作符*，弹出栈中优先级高于或等于*的（但栈顶为左括号，无需弹出），最后*入栈
    • 操作符栈为[+ ( *]，后缀表达式为"1 2 3 * - 4"
    1. 遇到左括号(，左括号入栈
    • 操作符栈为[+ ( * (]，后缀表达式为"1 2 3 * - 4"
    1. 遇到操作数5，添加到后缀表达式中
    • 操作符栈为[+ ( * (]，后缀表达式为"1 2 3 * - 4 5"
    1. 遇到操作符-，弹出栈中优先级高于或等于-的（但栈顶为左括号，无需弹出），最后-入栈
    • 操作符栈为[+ ( * ( -]，后缀表达式为"1 2 3 * - 4 5"
    1. 遇到操作数6，添加到后缀表达式中
    • 操作符栈为[+ ( * ( -]，后缀表达式为"1 2 3 * - 4 5 6"
    1. 遇到右括号)，依次弹出栈中操作符，直到遇到左括号，左右括号均不添加到后缀表达式中
    • 操作符栈为[+ ( *]，后缀表达式为"1 2 3 * - 4 5 6 -"
    1. 遇到操作符+，弹出栈中优先级高于或等于+的（*），最后+入栈
    • 操作符栈为[+ ( +]，后缀表达式为"1 2 3 * - 4 5 6 - *"
    1. 遇到操作数7，添加到后缀表达式中
    • 操作符栈为[+ ( +]，后缀表达式为"1 2 3 * - 4 5 6 - * 7"
    1. 遇到右括号)，依次弹出栈中操作符，直到遇到左括号，左右括号均不添加到后缀表达式中
    • 操作符栈为[+]，后缀表达式为"1 2 3 * - 4 5 6 - * 7 +"
    1. 遇到除号/，弹出栈中优先级高于或等于/的（无），最后/入栈
    • 操作符栈为[+ /]，后缀表达式为"1 2 3 * - 4 5 6 - * 7 +"
    1. 遇到操作数8，添加到后缀表达式中
    • 操作符栈为[+ /]，后缀表达式为"1 2 3 * - 4 5 6 - * 7 + 8"
    1. 遇到操作符+，弹出栈中优先级高于或等于+的（/ +），最后+入栈
    • 操作符栈为[+]，后缀表达式为"1 2 3 * - 4 5 6 - * 7 + 8 / +"
    1. 遇到操作数9，添加到后缀表达式中
    • 操作符栈为[+]，后缀表达式为"1 2 3 * - 4 5 6 - * 7 + 8 / + 9"
    1. 依次弹出栈中剩余元素
    • 操作符栈为[]，后缀表达式为"1 2 3 * - 4 5 6 - * 7 + 8 / + 9 +"

    结束

    1. class Solution {
    2. public:
    3.     /**
    4.      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    5.      * 返回表达式的值
    6.      * @param s string字符串 待计算的表达式
    7.      * @return int整型
    8.      */
    9.     int solve(string s) {
    10.         // write code here
    11.         vector<string> infOrder, sufOrder;
    12.         this->strParser(s, infOrder);
    13.         printVector(infOrder);
    14.         this->infill2suffix(infOrder, sufOrder);
    15.         printVector(sufOrder);
    16.         return this->suffix2val(sufOrder);
    17.     }
    19.     int suffix2val(vector<string>& sufOrder){
    20.         // 后缀表达式求值
    21.         stack<int> numStack;
    22.         int a, b;
    23.         for(string str : sufOrder){
    24.             if(isOperator(str)){
    25.                 b = numStack.top();
    26.                 numStack.pop();
    27.                 a = numStack.top();
    28.                 numStack.pop();
    29.                 if(str == "+"){
    30.                     numStack.push(a + b);
    31.                 }else if(str == "-"){
    32.                     numStack.push(a - b);
    33.                 }else if(str == "*"){
    34.                     numStack.push(a * b);
    35.                 }else{
    36.                     numStack.push(a / b);
    37.                 }
    38.             }
    39.             else{
    40.                 numStack.push(atoi(str.c_str()));
    41.             }
    42.         }
    43.         return numStack.top();
    44.     }
    46.     void infill2suffix(vector<string>& infOrder, vector<string>& sufOrder){
    47.         // 中缀表达式转后缀表达式
    48.         sufOrder.clear();
    49.         stack<string> opStack;
    50.         for(string str : infOrder){
    51.             if(isOperator(str)){
    52.                 if(opStack.empty() || str=="("){
    53.                     opStack.push(str);
    54.                 }
    55.                 else if(str == ")"){
    56.                     while(opStack.top() != "("){
    57.                         sufOrder.push_back(opStack.top());
    58.                         opStack.pop();
    59.                     }
    60.                     opStack.pop();
    61.                 }
    62.                 else{
    63.                     while(!opStack.empty() && isHigherOperator(opStack.top(), str)){
    64.                         sufOrder.push_back(opStack.top());
    65.                         opStack.pop();
    66.                     }
    67.                     opStack.push(str);
    68.                 }
    69.             }
    70.             else{
    71.                 sufOrder.push_back(str);
    72.             }
    73.         }
    74.         while(!opStack.empty()){
    75.             sufOrder.push_back(opStack.top());
    76.             opStack.pop();
    77.         }
    78.     }
    80.     void strParser(string& s, vector<string>& ret){
    81.         // 解析字符串，将数字和符号分开
    82.         string curStr = "";
    83.         for(char ch : s){
    84.             if(ch >= '0' && ch <= '9'){
    85.                 curStr += ch;
    86.             }
    87.             else{
    88.                 if(curStr != ""){
    89.                     ret.push_back(curStr);
    90.                 }
    91.                 ret.push_back(string(1, ch));
    92.                 curStr = "";
    93.             }
    94.         }
    95.         if(curStr != ""){
    96.             ret.push_back(curStr);
    97.         }
    98.     }
    100.     bool isOperator(string& op){
    101.         for(int i=0; i<this->ops.size(); i++){
    102.             if(op == this->ops[i]){
    103.                 return true;
    104.             }
    105.         }
    106.         return false;
    107.     }
    109.     bool isHigherOperator(string& op1, string& op2){
    110.         // 判断op1是否比op2的优先级较高
    111.         return this->opsPriority[op1] >= this->opsPriority[op2];
    112.     }
    115. private:
    116.     vector<string> ops={"+", "-", "*", "/", "(", ")"};
    117.     map<string, int> opsPriority = {
    118.         {"(", 0},
    119.         {"+", 1}, {"-", 1},
    120.         {"*", 2}, {"/", 2}
    121.     };
    122. };