计算后缀表达式（逆波兰表达式）

后缀表达式（也称为逆波兰表达式）是一种数学表达式，其中运算符位于其操作数之后。例如，表达式 3 4 + 表示 3 + 4。计算后缀表达式可以使用栈来实现。以下是完整的代码实现，包括关键行注释和示例。

1. 算法思想

计算后缀表达式的核心思想是使用栈来存储操作数，并按照以下步骤进行：

初始化：

• 创建一个空栈 S 用于存储操作数。

遍历后缀表达式：

• 从左到右遍历后缀表达式的每个元素。
• 如果当前元素是一个操作数，则将其压入栈中。
• 如果当前元素是一个运算符，则从栈中弹出两个操作数，进行相应的运算，并将结果压回栈中。

结果：

• 遍历完整个表达式后，栈中剩下的唯一一个元素即为表达式的计算结果。

2. 图示法表示步骤

假设我们有以下后缀表达式：

5 1 2 + 4 * + 3 -

步骤 1：初始化

• 创建一个空栈 S。

步骤 2：遍历后缀表达式

元素 5：

• 操作数，压入栈中。
• 栈: [5]

元素 1：

• 操作数，压入栈中。
• 栈: [5, 1]

元素 2：

• 操作数，压入栈中。
• 栈: [5, 1, 2]

元素 +：

• 运算符，弹出两个操作数 1 和 2，计算 1 + 2 = 3，将结果 3 压入栈中。
• 栈: [5, 3]

元素 4：

• 操作数，压入栈中。
• 栈: [5, 3, 4]

元素 *：

• 运算符，弹出两个操作数 3 和 4，计算 3 * 4 = 12，将结果 12 压入栈中。
• 栈: [5, 12]

元素 +：

• 运算符，弹出两个操作数 5 和 12，计算 5 + 12 = 17，将结果 17 压入栈中。
• 栈: [17]

元素 3：

• 操作数，压入栈中。
• 栈: [17, 3]

元素 -：

• 运算符，弹出两个操作数 17 和 3，计算 17 - 3 = 14，将结果 14 压入栈中。
• 栈: [14]

最终结果

• 栈中剩下的元素为 14，即表达式的计算结果。

3. 代码实现

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define MAXSIZE 100

// 栈结构体
typedef struct {
    int data[MAXSIZE];
    int top;
} Stack;

// 初始化栈
void InitStack(Stack* S) {
    S->top = -1;
}

// 判断栈是否为空
int IsEmpty(Stack* S) {
    return S->top == -1;
}

// 入栈
void Push(Stack* S, int x) {
    if (S->top < MAXSIZE - 1) {
        S->data[++(S->top)] = x;
    } else {
        printf("Stack overflow!\n");
        exit(1);
    }
}

// 出栈
int Pop(Stack* S) {
    if (!IsEmpty(S)) {
        return S->data[(S->top)--];
    } else {
        printf("Stack underflow!\n");
        exit(1);
    }
}

// 计算后缀表达式
int evaluatePostfix(char* expr) {
    Stack S;
    InitStack(&S);
    int i = 0;
    while (expr[i] != '\0') {
        if (isdigit(expr[i])) { // 如果是数字
            Push(&S, expr[i] - '0'); // 将数字压入栈中
        } else { // 如果是运算符
            int b = Pop(&S); // 弹出第二个操作数
            int a = Pop(&S); // 弹出第一个操作数
            switch (expr[i]) {
                case '+': Push(&S, a + b); break;
                case '-': Push(&S, a - b); break;
                case '*': Push(&S, a * b); break;
                case '/': Push(&S, a / b); break;
                default: printf("Invalid operator!\n"); exit(1);
            }
        }
        i++;
    }
    return Pop(&S); // 返回结果
}

int main() {
    char expr[] = "5 1 2 + 4 * + 3 -"; // 后缀表达式
    int result = evaluatePostfix(expr); // 计算结果
    printf("Result: %d\n", result); // 输出结果
    return 0;
}

4. 代码关键行注释

int evaluatePostfix(char* expr) {
    Stack S;
    InitStack(&S); // 初始化栈
    int i = 0;
    while (expr[i] != '\0') { // 遍历后缀表达式
        if (isdigit(expr[i])) { // 如果是数字
            Push(&S, expr[i] - '0'); // 将数字压入栈中
        } else { // 如果是运算符
            int b = Pop(&S); // 弹出第二个操作数
            int a = Pop(&S); // 弹出第一个操作数
            switch (expr[i]) { // 根据运算符进行计算
                case '+': Push(&S, a + b); break;
                case '-': Push(&S, a - b); break;
                case '*': Push(&S, a * b); break;
                case '/': Push(&S, a / b); break;
                default: printf("Invalid operator!\n"); exit(1);
            }
        }
        i++;
    }
    return Pop(&S); // 返回结果
}

5. 时间复杂度

• 时间复杂度：
  • 遍历后缀表达式一次，时间复杂度为O(n)，其中 n 是表达式的长度。

6. 空间复杂度

• 空间复杂度：
  • 使用了一个栈，空间复杂度为 O(n)。

7. 总结

通过使用栈，可以高效地计算后缀表达式。该算法的时间复杂度为线性级别，空间复杂度为线性级别，适用于各种大小的表达式计算。