中缀表达式转后缀表达式求值。

简介

中缀表达式很适合人类的思维，但是对计算机来说并不好理解，我们需要把它转为后缀表达式。

后缀表达式求值。

后缀表达式也叫波兰逆序表达式。求值过程可以用栈来模拟。

• 依次读入后缀表达式
• 遇到数字则压入栈中
• 遇到运算符则取出两个数字进行运算
• 直到剩最后一个数字即是答案。

中缀表达式求后缀表达式。

• 依次读取中缀表达式。
• 遇到数字则输出。
• 遇到左括号则压入栈中。
• 遇到右括号则依次弹出（输出）栈中的操作符，直至遇到左括号，并将左括号也弹出，但并不输出。
• 遇到操作符，和栈顶比较
  • 若栈空，则压入操作符。
  • 若栈顶为左括号，则压入操作符。
  • 若栈顶也为操作符，则依次弹出所有优先级不比当前元素小（即优先级大于等于当前元素的栈顶元素）的操作符，直至遇到左括号或栈空。然后压入当前操作符。
• 若结束，而栈中还有操作符，则依次弹出（输出）所有操作符。

这道题中，我们把所有的输出过程存入队列（或数组）中，然后在对后缀表达式求值即可

代码如下

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

stack<char> stk;
stack<int> ans;
char str[N];
queue<char> que;

bool is_num(char c) { //判断是否是数字
    return c >= '0' && c <= '9';
}

bool pro(char c1, char c2) { // 判断c1是否大于c2
    return (c1 == '*' || c1 == '/') && (c2 == '+' || c2 == '-');
}

int main() {
    scanf("%s", str);
    for(int i = 0; str[i]; ++i) {
        if(is_num(str[i])) { //由于栈或队列只能存纯char或纯int，遇到多位的数字不好处理，这里用.来表示数字结束
            do {
                que.push(str[i++]);
            }
            while(is_num(str[i]));
            que.push('.');
            i--;
        }
        else if(str[i] == '(') stk.push(str[i]);
        else if(str[i] == ')') {
            while(stk.top() != '(') {
                que.push(stk.top());
                stk.pop();
            }
            stk.pop();
        }
        else if(stk.empty() || stk.top() == '(') {
            stk.push(str[i]);
        }
        else if(!pro(str[i], stk.top())) {
            //注意优先级相同也要弹出，所以这里反着传参并取非了。
            while(!stk.empty() && stk.top() != '(' && !pro(str[i], stk.top())) {
                que.push(stk.top());
                stk.pop();
            }
            stk.push(str[i]);
        }
        else {
            stk.push(str[i]);
        }
    }
    while(!stk.empty()) {
        //如果stk有剩余，全部弹出，至此，中缀转后缀完成
        que.push(stk.top());
        stk.pop();
    }

    //这里是我调试的，不用管
    // while(!que.empty()) {
    //     printf("%c", que.front());
    //     que.pop();
    // }
    // return 0;


    //以下为后缀表达式求值
    while(!que.empty()) {
        int n = 0;
        if(is_num(que.front())) {
            //由于上面对数字做了结束的处理，这里可以很方便地读取每个多位的数字，多个数字连一起也可以区分。
            do {
                n *= 10;
                n += que.front() - '0';
                que.pop();
            }
            while(que.front() != '.');
            que.pop();
            ans.push(n);
            n = 0;
        }
        else {
            int n2 = ans.top(); ans.pop(); //注意运算顺序，后弹出的与先弹出的运算。
            int n1 = ans.top(); ans.pop();
            if(que.front() == '+') ans.push(n1 + n2);
            else if(que.front() == '-') ans.push(n1 - n2);
            else if(que.front() == '*') ans.push(n1 * n2);
            else ans.push(n1 / n2);
            que.pop();
        }
    }

    printf("%d", ans.top()); //输出还留在栈里的最后一个值，便是答案
    return 0;
}