栈在表达式中的应用

中缀表达式转后缀表达式

中缀转后缀核心目标：去除括号，并根据运算符的优先级，将运算符移到其两个操作数的后面。

转换规则

1. 遇操作数：

   • 直接输出到后缀表达式中。

2. 遇左括号 (：

   • 直接压入运算符栈。

3. 遇右括号 )：

   • 依次将栈顶的运算符弹出并输出，直到遇到左括号 ( 为止。
   • 将弹出的左括号 ( 丢弃。

4. 遇运算符（+, -, *, /）：

   • 如果栈为空，或栈顶为 (，直接将该运算符入栈。
   • 如果栈顶也是运算符：
     • 若当前运算符的优先级 高于 栈顶运算符的优先级，将当前运算符入栈。
     • 若当前运算符的优先级 小于等于 栈顶运算符的优先级，不断弹出栈顶运算符并输出，直到栈空、遇到 (，或者栈顶运算符优先级低于当前运算符，然后再将当前运算符入栈。

后缀表达式求值

后缀表达式完全不需要考虑优先级和括号。

求值规则

1. 遇操作数（数字）：

   • 直接压入操作数栈。

2. 遇运算符（+, -, *, /）：

   • 从栈中依次弹出两个操作数：

   • 先弹出的作为右操作数 $B$；

   • 后弹出的作为左操作数 $A$。

   • 计算 $A \text{ [运算符]} B$ 的结果。

   • 将计算得到的中间结果压回操作数栈中。

   • 遍历结束：

   • 栈中最后剩下的那一个数值，就是该表达式的最终计算结果。

具体代码

#include <iostream>
#include <stack>
#include <vector>
#include <string>

struct Node { 
    int x;
    char c = 'i';
};


std::vector<Node> Convert(const std::string &S) {
    std::stack<Node> stack;
    std::vector<Node> Express;
    std::vector<Node> Ex;
    
    for (int i = 0; i < S.size();) {
        if (S[i] == ' ') {      //遇到空格跳过
            i++;
        } else if (S[i] >= '0' && S[i] <= '9') {        //如果为数字
            int num = 0;

            while (i < S.length() && S[i] >= '0' && S[i] <= '9') {      //获取完整的数字
                num = num * 10 + (S[i] - '0');
                i++;
            }

            Ex.push_back({num, 'i'});       
        } else {
            if (S[i] == '-') {      //如果是减号，在前面是(，或者为空的情况下插入负号
                if (Ex.empty() || Ex.back().c == '(') {
                    Ex.push_back({0, 'i'});
                }
            } 
                Ex.push_back({0, S[i]});
                i++;
        }
    }

    for (int i = 0; i < Ex.size(); ++i) {       
        if (Ex[i].c == 'i') {
            std::cout << Ex[i].x << " ";
        } else {
            std::cout << Ex[i].c << " ";
        }
    }


    for (int i = 0; i < Ex.size(); ++i) {
        if (Ex[i].c == 'i') {
            Express.push_back(Ex[i]);       //如果为'i'，说明是数字，直接加入表达式
        } else {
            if (Ex[i].c == '(') {       //为左括号，直接压入栈
                stack.push(Ex[i]);
            } else if (Ex[i].c == ')') {    //为右括号，从栈中弹出符号，直到遇到左括号
                while (stack.top().c != '(') {
                    Express.push_back(stack.top());
                    stack.pop();
                }
                stack.pop();
            } else {    
                if (Ex[i].c == '+' || Ex[i].c == '-') {     //如果为符号，若比栈顶运算优先级高或者栈顶为左括号，直接压入栈；如果等于或低于栈顶负号，则弹出栈顶元素直到栈为空或遇到更低优先级的负号或遇到左括号，再将当前运算符压入
                    if (stack.empty()) {
                        stack.push(Ex[i]);
                    } else if (stack.top().c == '(') {
                        stack.push(Ex[i]);
                    } else {
                        while (!stack.empty() && stack.top().c != '(') {
                            Express.push_back(stack.top());
                            stack.pop();
                            if (stack.empty()) {
                                break;
                            }
                        }
                        stack.push(Ex[i]);
                    }
                } else {
                    if (stack.empty()) {
                        stack.push(Ex[i]);
                    } else if (stack.top().c == '+' || stack.top().c == '-' || stack.top().c == '(') {
                        stack.push(Ex[i]);
                    } else {
                        while (!stack.empty() && (stack.top().c == '*' || stack.top().c == '/')) {
                            Express.push_back(stack.top());
                            stack.pop();
                        }
                        stack.push(Ex[i]);
                    }
                }
            }
        }
    }
    while (!stack.empty()) {
        Express.push_back(stack.top());
        stack.pop();
    }
    return Express;
}

int Calculate(const std::vector<Node> &Ex) {
    std::stack<int> stack;

    for (int i = 0; i < Ex.size(); ++i) {
        if (Ex[i].c == 'i') {
            stack.push(Ex[i].x);
        } else {
            int b = stack.top();
            stack.pop();
            int a = stack.top();
            stack.pop();
            int c;
            if (Ex[i].c == '*') {
                c = a * b;
            } else if (Ex[i].c == '/') {
                c = a / b;
            } else if (Ex[i].c == '+') {
                c = a + b;
            } else if (Ex[i].c == '-'){
                c = a - b;
            }
            stack.push(c);
        }
    }
    return stack.top();
}

int main() {
    std::string S = "1+2*(-3)*4";
    
    std::vector<Node> N = Convert(S);

    std::cout << std::endl;

    for (const auto &x : N) {
        if (x.c != 'i') {
            std::cout << x.c << " ";
        } else {
            std::cout << x.x << " ";
        }
    }
    std::cout << std::endl;
    int c = Calculate(N);
    std::cout << c << std::endl;
    return 0;
}