平常写表达式，一般运算符在数的中间，比如 \(1 + 3 \times 5\)，其中 \(+\) 在 \(1\) 和 \(3 \times 5\) 之间，\(\times\) 在 \(3\) 和 \(5\) 中间，这种表达式称为中缀表达式。中缀表达式对人类友好，但对计算机没那么友好。对计算机友好的表达式是“后缀表达式”，顾名思义，后缀表达式中运算符在参数的后面。对于计算机而言，后缀表达式比中缀表达式更容易计算，另外，后缀表达式的运算机制可以避免掉括号，这也是它相对于中缀表达式的一大优势。

计算题：中缀表达式 ((6-3)*2+7)/(5^(3*4+2)) 对应的后缀表达式为？

选择题：表达式 a*d-b*c 的前缀形式是？

• A. ad*bc*-
• B. -*ad*bc
• C. a*d-b*c
• D. -**adbc

B。

转换的核心是遵循运算符的优先级。

在表达式 a*d - b*c 中，乘法 * 的优先级高于减法 -。因此，必须先计算两个乘法，再计算减法。可以为表达式加上括号来明确这个运算顺序：((a * d) - (b * c))。

中缀表达式 (a * d) 转前缀则是将运算符 * 提到前面，得到 * a d。同理，中缀表达式 (b * c) 转换成前缀表达式得到 * b c。

经过上一步，表达式现在可以看作是 (子表达式1) - (子表达式2)，而这个表达式转前缀将运算符 - 提到最前面，得到 - 子表达式1 子表达式2。

所以最终结果是：- * a d * b c。

后缀表达式求值

栈的一大用处是做算术表达式的计算，对于计算机来讲，它最容易理解后缀表达式，可以使用栈来 \(O(N)\) 地求出它的值。

1. 建立一个用于存数的栈，逐一扫描该后缀表达式中的元素。
   • 如果遇到一个数，则把该数入栈。
   • 如果遇到运算符，就取出栈顶的两个数进行计算，把结果入栈。
2. 扫描完成后，栈中恰好剩下一个数，就是该后缀表达式的值。

以后缀表达式 2 4 * 1 3 + - 为例：首先从左往右读式子，读到了乘号。乘法有两个参数，所以取出前面的 2 和 4，算出 \(2 \times 4 = 8\)。于是可以擦掉 2 4 *，写上 8，式子变成 8 1 3 + -。读到加号之后，取出前面的 1 和 3，算出 \(1+3=4\)，把式子改写成 8 4 -。接着读到减号之后取出 8 和 4，算出 \(8-4=4\)，于是最后的式子就是 4，这就是期望的结果。

例题：P1449 后缀表达式

#include <cstdio>
#include <cstring>
#include <stack>
using std::stack;
const int N = 55;
char s[N];
int main()
{
	scanf("%s", s + 1);
	int len = strlen(s + 1);
	int num=0;
	stack<int> st; // 存储运算数的栈
	for (int i = 1; i <= len; i++) {
		if (s[i]>='0'&&s[i]<='9') {
			// 更新数字
			num=num*10+(s[i]-'0');
		} else if (s[i]=='.') {
			// num就作为一个运算的数字加入到栈中
			st.push(num);
			num=0;
		} else if (s[i]=='@') {
			break;
		} else {
			// +-*/
			// 取出栈顶的两个元素
			// top() 表示取栈顶
			// pop() 表示弹出栈顶
			// empty() 返回一个栈是否为空
			// true对应空，false对应非空
			int x=st.top(); st.pop();
			int y=st.top(); st.pop();
			// x和y就是最近两次压入栈中的运算数
			int z;
			if (s[i]=='+') {
				z=y+x;
			} else if (s[i]=='-') {
				z=y-x;
			} else if (s[i]=='*') {
				z=y*x;
			} else {
				z=y/x;
			}
			st.push(z);
		}
	}
	printf("%d\n", st.top());
    return 0;
}

中缀表达式转后缀表达式

如果想让计算机求解人类常用的中缀表达式的值，最快的办法就是把中缀表达式转化成后缀表达式，再进行后缀表达式求值的方法，这个转化过程同样可以使用栈来 \(O(N)\) 地完成。

调度场算法

调度场算法由 Edsger Dijkstra 发明，用于将中缀表达式转换为后缀表达式。在这个过程中配合后缀表达式求值的原理，即可通过一次扫描求出原始的中缀表达式的计算结果。

核心概念

双栈设计

为了直接求值，维护两个栈：

1. 操作数栈：存储解析出的数字。
2. 运算符栈：存储待执行的运算符和左括号。

运算符优先级

不同运算符有不同的优先级，决定了计算的顺序。例如：

• 最高：^（幂运算）
• 次高：-（一元负号）
• 中等：*、/
• 最低：+、-

结合性

当两个运算符优先级相同时，结合性决定了计算方向：

• 左结合：从左向右算，例如 a - b - c 等价于 (a - b) - c，大多数运算符（加减乘除）都是左结合。
• 右结合：从右向左算，例如 a ^ b ^ c 等价于 a ^ (b ^ c)，幂运算通常是右结合。

算法流程

从左到右扫描表达式字符串，根据字符类型执行不同操作：

1. 数字处理：如果遇到数字，解析完整的数值并压入操作数栈。
2. 左括号：直接压入运算符栈，它起到隔离作用，直到遇到右括号。
3. 右括号：不断弹出运算符栈栈顶的运算符并执行计算，直到遇到左括号，这步操作将括号内的表达式全部归约为一个数值。
4. 运算符处理：这是算法的核心。
   • 区分负号和减号：- 既可以是减号（二元），也可以是负号（一元）。策略：维护一个 flag 变量，初始为 true，遇到 ( 或运算符置 true，遇到数字或 ) 置 false，如果读到 - 且 flag 等于 true，则将其改为一个特殊标记（例如用 @ 替代一元负号）。
   • 调度逻辑
     • 如果是一元负号，直接入栈（因为它是右结合且优先级很高，等待后面的数字）。
     • 如果是二元运算符，需要维护栈内优先级的单调性，循环检查运算符栈的栈顶元素：
       • 如果栈顶优先级高，必须先算栈顶。
       • 如果和栈顶优先级一样大：对于左结合运算，栈顶先算；对于右结合运算，栈顶后算（因为要等右边的结果），所以跳出循环，当前运算符入栈。
       • 如果栈顶优先级低，当前优先级高，跳出循环，当前运算符入栈。

例题：P10473 表达式计算4

#include <cstdio>
#include <stack>
#include <cstring>
#include <cctype>
using namespace std;

const int N = 35;
char s[N];
stack<int> nums; // 数字栈
stack<char> ops; // 运算符栈

// 计算 x^y
int power(int x, int y) {
    if (x == 1 || x == 0) return x;
    if (x == -1) return y % 2 ? -1 : 1;
    int res = 1;
    for (int i = 0; i < y; i++) res *= x;
    return res;
}

// 执行一次栈顶运算
void calc() {
    if (ops.empty()) return;
    char op = ops.top(); ops.pop();
    
    // 处理一元负号 '@'
    if (op == '@') {
        if (nums.empty()) return;
        int a = nums.top(); nums.pop();
        nums.push(-a);
    } else {
        // 处理二元运算符
        if (nums.size() < 2) return;
        int b = nums.top(); nums.pop();
        int a = nums.top(); nums.pop();
        
        int res = 0;
        if (op == '+') res = a + b;
        else if (op == '-') res = a - b;
        else if (op == '*') res = a * b;
        else if (op == '/') res = a / b;
        else if (op == '^') res = power(a, b);
        
        nums.push(res);
    }
}

// 获取运算符优先级
int get(char op) {
    if (op == '^') return 4; // 幂运算优先级最高
    if (op == '@') return 3; // 一元负号优先级次之
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

int main()
{
    scanf("%s", s);

    // flag 用于标记下一个 '-' 是否应视为负号
    // 初始为 true，遇到左括号或运算符后也为 true，遇到数字或右括号后为 false
    bool flag = true;
    int n = strlen(s);
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            ops.push('(');
            flag = true; // 左括号后可能是负号，如 (-5)
        } else if (s[i] == ')') {
            // 计算括号内的所有运算
            while (!ops.empty() && ops.top() != '(') calc();
            if (!ops.empty()) ops.pop(); // 弹出左括号
            flag = false; // 右括号后通常接二元运算符，不能接一元负号
        } else if (isdigit(s[i])) {
            int val = 0;
            // 解析多位数字
            while (i < n && isdigit(s[i])) {
                val = val * 10 + (s[i] - '0');
                i++;
            }
            i--; // 回退，因为循环体外还有 i++
            nums.push(val);
            flag = false; // 数字后期待二元运算符
        } else {
            char op = s[i];
            // 关键逻辑：如果当前字符是 '-' 且 flag 为 true，则转化为一元负号 '@'
            if (op == '-' && flag) op = '@';
            
            if (op == '@') {
                ops.push(op); // 一元运算符直接入栈
            } else {
                // 二元运算符，维护单调性（调度场算法）
                int p = get(op);
                while (!ops.empty() && ops.top() != '(') {
                    char opt = ops.top();
                    int pt = get(opt);
                    // 如果栈顶优先级高于当前，或者相等（左结合），则先计算栈顶
                    // 注意：^ 是右结合的，所以如果当前是 ^ 且栈顶也是 ^ (优先级相等)，不能先计算栈顶
                    if (pt > p) {
                        calc();
                    } else if (pt == p) {
                        if (op == '^') break; // 右结合，不弹出
                        calc();
                    } else {
                        break;
                    }
                }
                ops.push(op);
            }
            flag = true; // 运算符后期待数字或一元符号
        }
    }
    // 计算剩余的运算
    while (!ops.empty()) calc();
    if (!nums.empty()) printf("%d\n", nums.top());
    return 0;
}