后缀表达式的计算方法

    1. 如果遇到操作数，将其压入操作数栈中；
    2. 如果遇到操作符，弹出操作数栈顶元素b，再弹出下一个操作数栈顶元素a，执行运算a 操作符 b，并将结果入栈；
    3. 最后操作数栈只剩最后一个元素，即为表达式的值

    示例：1 2 3 * - 4 5 6 - * 7 + 8 / + 9 +

    1. 1 2 3 依次入栈
    • 操作数栈为[1 2 3]
    1. 遇到操作符，弹出3、弹出2，执行23，结果为6，6入栈
    • 操作数栈为[1 6]
    1. 遇到操作符-，弹出6、弹出1，执行1-6，结果为-5，-5入栈
    • 操作数栈为[-5]
    1. 4 5 6 依次入栈
    • 操作数栈为[-5 4 5 6]
    1. 遇到操作符-，弹出6、弹出5，执行5-6，结果为-1，-1入栈
    • 操作数栈为[-5 4 -1]
    1. 遇到操作符，弹出-1、弹出4，执行4-1，结果为-4，-4入栈
    • 操作数栈为[-5 -4]
    1. 7入栈
    • 操作数栈为[-5 -4 7]
    1. 遇到操作符+，弹出7、弹出-4，执行7+-4，结果为3，3入栈
    • 操作数栈为[-5 3]
    1. 8入栈
    • 操作数栈为[-5 3 8]
    1. 遇到操作符/，弹出8、弹出3，执行3/8，结果为0，0入栈
    • 操作数栈为[-5 0]
    1. 遇到操作符+，弹出0、弹出-5，执行-5+0，结果为-5，-5入栈
    • 操作数栈为[-5]
    1. 9入栈
    • 操作数栈为[-5 9]
    1. 遇到操作符+，弹出9、弹出-5，执行-5+9，结果为4，4入栈
    • 操作数栈为[4]
    1. 表达式最终值为4

    结束

    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. };