前言

今天来讲一下栈的应用，如何利用栈来进行简单的整数型表达式求值。

表达式由操作数(Operand)、运算符(operator)和界限符(delimiter)组成。

中缀表达式就是平常我们计算的正常式子。

我们讲的整数型简单表达式只包括整型，加减乘除和左右括弧。

算法

思考引入

首先我们想像一下我们是如何计算式子的，在简单表达式中我们按照如下步骤计算：

1. 先计算括号内的算式。
2. 先乘除后加减。
3. 平级运算符从左往右顺序计算。

按照这个想法，我们想一下程序要如何计算算式，它无法像人一样直接看到整个算式，而是只能从左往右看，以下面这个算式为例，我们模拟一下计算机的想法。

步骤如下

1. 从左到右看到的时候，我们只能保留，因为后面可以有更高优先级的运算符。
2. 看到的时候，我们可以直接计算得到5，因为括号内的表达式应该最先计算，现在是，然而此时我们仍然不能计算这部分算式得出结果，因为我们无法确定后面是否有平级或者优先级更高的算式，那些部分需要先计算，如果现在先计算后面有乘号就会导致错误。
3. 看到的时候我们可以计算前面这部分式子了，因为我们看到后面出现了更低优先级的表达式，所以计算前后都是低优先级中间是高优先级，得到式子。
4. 最后看完式子为结束，看到最后一个加号可以先计算了。

从上面可以发现，我们需要保证局部表达式在中间是高优先级两边是低优先级的时候方可计算这部分式子，因此可以有下面这套算法思想来指导我们编写相关程序。

算法思想

1. 我们需要初始两个栈：OPTR栈-寄存运算符，OPND栈-寄存操作数。
2. 首先在OPTR栈底放入起始符号'#'作为栈底元素（可选）。
3. 然后依次读入表达式字符，遵守以下规则：
   1. 如果读入的是操作数，压入OPND栈。
   2. 如果读入的是运算符：
      1. 如果是左括号'('，直接压入OPTR栈顶，因为这是优先级最高的。
      2. 如果是右括号')'，一直弹出OPTR栈顶和OPND栈顶两个元素做运算，直到OPTR栈顶元素会左括号'('，弹出结束。
      3. 如果是运算符，和当前OPTR栈顶元素做优先级比较：如果当前运算符优先级大于栈顶元素，直接压入栈顶；如果当前运算符优先级小于等于栈顶元素，将OPTR栈顶元素和OPND栈顶两个元素弹出做运算，得出结果压入OPND栈顶。
4. 重复以上步骤，直到表达式结束，OPND栈顶只有一个数字，OPTR栈顶只有'#'号。

注意思考时可能会觉得有些情况不能处理，但是其实这些情况不会发生，因为我们会及时处理局部的运算

比如可能会觉得代码逻辑会处理掉部分导致错误，但是其实这时候表示式会变为处理，因为我们已经处理了局部的乘法运算。

代码实现

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

#define MAX_STACK_SIZE 100

// 判断运算符优先级
int precedence(char op) {
    switch (op) {
    case '+':
    case '-':
        return 1; // 加减号1级
    case '*':
    case '/':
        return 2; // 乘除号2级
    default:
        return 0; // 默认0级
    }
}

// 执行运算
int applyOperator(char op, int a, int b) {
    switch (op) {
    case '+': return a + b;
    case '-': return a - b;
    case '*': return a * b;
    case '/':
        if (b == 0) {
            printf("错误: 除以零\n");
            exit(EXIT_FAILURE);
        }
        return a / b;
    case '#':
        printf("结束运算\n"); // #号结束运算
        exit(EXIT_SUCCESS);
    default:
        printf("错误: 无效的运算符 '%c'\n", op);
        exit(EXIT_FAILURE);
    }
}

// 打印栈的内容
void printStacks(char* optrStack, int optrTop, int* opndStack, int opndTop) {
    printf("OPTR栈: ");
    if (optrTop == -1) {
        printf("空");
    }
    else {
        for (int i = 0; i <= optrTop; i++) {
            printf("%c ", optrStack[i]);
        }
    }

    printf("\nOPND栈: ");
    if (opndTop == -1) {
        printf("空");
    }
    else {
        for (int i = 0; i <= opndTop; i++) {
            printf("%d ", opndStack[i]);
        }
    }
    printf("\n");
}

// 处理表达式
void evaluateExpression(const char* expression) {
    // 初始化optrStack和opndStack
    char* optrStack = (char*)malloc(MAX_STACK_SIZE * sizeof(char));
    int* opndStack = (int*)malloc(MAX_STACK_SIZE * sizeof(int));

    if (!optrStack || !opndStack) {
        printf("内存分配失败\n");
        exit(EXIT_FAILURE);
    }

    // 初始化optrStack和opndStack的指针
    int optrTop = -1;
    int opndTop = -1;

    // 将 '#' 作为结束符放入 optrStack
    optrStack[++optrTop] = '#';

    int i = 0;
    char token;

    printf("表达式: %s\n", expression);

    while ((token = expression[i]) != '\0') {
        // 跳过空格
        if (isspace(token)) {
            i++;
            continue;
        }

        printf("\n读取字符: %c\n", token);

        // 如果是数字，处理多位数字
        if (isdigit(token)) {
            int num = 0;
            // 循环直到遇到运算符
            while (isdigit(expression[i])) {
                num = num * 10 + (expression[i] - '0');
                i++;
            }
            if (opndTop >= MAX_STACK_SIZE - 1) {
                printf("错误: 操作数栈溢出\n");
                free(optrStack);
                free(opndStack);
                exit(EXIT_FAILURE);
            }
            // 将数字压入OPND栈顶
            opndStack[++opndTop] = num;
            printf("将操作数 %d 压入 OPND 栈\n", num);
            printStacks(optrStack, optrTop, opndStack, opndTop);
            continue;
        }

        // 如果是左括号，直接压入 OPTR 栈顶
        if (token == '(') {
            if (optrTop >= MAX_STACK_SIZE - 1) {
                printf("错误: 运算符栈溢出\n");
                free(optrStack);
                free(opndStack);
                exit(EXIT_FAILURE);
            }
            optrStack[++optrTop] = token;
            printf("将 '(' 压入 OPTR 栈\n");
            printStacks(optrStack, optrTop, opndStack, opndTop);
            i++;
            continue;
        }

        // 如果是右括号，处理括号内的所有运算
        if (token == ')') {
            printf("遇到 ')'，处理括号内的所有运算\n");
            // 一直循环直到OPTR栈顶没有操作符或者遇到做括号'('
            while (optrTop >= 0 && optrStack[optrTop] != '(') {
                if (optrTop < 0 || opndTop < 1) {
                    printf("错误: 表达式不合法\n");
                    free(optrStack);
                    free(opndStack);
                    exit(EXIT_FAILURE);
                }
                // 压出OPTR栈顶运算符
                char op = optrStack[optrTop--];
                // 压出OPND栈顶两个操作符
                int b = opndStack[opndTop--];
                int a = opndStack[opndTop--];
                // 得出运算结果压入OPND栈顶
                int result = applyOperator(op, a, b);
                if (opndTop >= MAX_STACK_SIZE - 1) {
                    printf("错误: 操作数栈溢出\n");
                    free(optrStack);
                    free(opndStack);
                    exit(EXIT_FAILURE);
                }
                opndStack[++opndTop] = result;
                printf("计算: %d %c %d = %d\n", a, op, b, result);
                printStacks(optrStack, optrTop, opndStack, opndTop);
            }
            if (optrTop < 0) {
                printf("错误: 括号不匹配\n");
                free(optrStack);
                free(opndStack);
                exit(EXIT_FAILURE);
            }
            optrTop--; // 弹出左括号
            printf("弹出 '(' \n");
            printStacks(optrStack, optrTop, opndStack, opndTop);
            i++;
            continue;
        }

        // 如果是运算符，并且小于等于栈顶元素那么一直循环直到碰到大于的栈顶元素再压入栈顶。
        while (optrTop >= 0 && precedence(optrStack[optrTop]) >= precedence(token) && optrStack[optrTop] != '#') {
            if (optrTop < 0 || opndTop < 1) {
                printf("错误: 表达式不合法\n");
                free(optrStack);
                free(opndStack);
                exit(EXIT_FAILURE);
            }
            char op = optrStack[optrTop--];
            int b = opndStack[opndTop--];
            int a = opndStack[opndTop--];
            int result = applyOperator(op, a, b);
            if (opndTop >= MAX_STACK_SIZE - 1) {
                printf("错误: 操作数栈溢出\n");
                free(optrStack);
                free(opndStack);
                exit(EXIT_FAILURE);
            }
            opndStack[++opndTop] = result;
            printf("计算: %d %c %d = %d\n", a, op, b, result);
            printStacks(optrStack, optrTop, opndStack, opndTop);
        }

        // 当前运算符压入栈
        if (optrTop >= MAX_STACK_SIZE - 1) {
            printf("错误: 运算符栈溢出\n");
            free(optrStack);
            free(opndStack);
            exit(EXIT_FAILURE);
        }
        optrStack[++optrTop] = token;
        printf("将运算符 '%c' 压入 OPTR 栈\n", token);
        printStacks(optrStack, optrTop, opndStack, opndTop);

        i++;
    }

    // 处理剩余的运算符
    while (optrTop >= 0 && optrStack[optrTop] != '#') {
        if (optrTop < 0 || opndTop < 1) {
            printf("错误: 表达式不合法\n");
            free(optrStack);
            free(opndStack);
            exit(EXIT_FAILURE);
        }
        char op = optrStack[optrTop--];
        int b = opndStack[opndTop--];
        int a = opndStack[opndTop--];
        int result = applyOperator(op, a, b);
        if (opndTop >= MAX_STACK_SIZE - 1) {
            printf("错误: 操作数栈溢出\n");
            free(optrStack);
            free(opndStack);
            exit(EXIT_FAILURE);
        }
        opndStack[++opndTop] = result;
        printf("计算: %d %c %d = %d\n", a, op, b, result);
        printStacks(optrStack, optrTop, opndStack, opndTop);
    }

    if (opndTop != 0) {
        printf("错误: 表达式不合法\n");
        free(optrStack);
        free(opndStack);
        exit(EXIT_FAILURE);
    }

    // 最终结果
    printf("\n最终结果: %d\n", opndStack[opndTop]);

    // 释放内存
    free(optrStack);
    free(opndStack);
}

int main() {
    const char* expression = "5+2*5+(6/3+7*3)+2 #";
    evaluateExpression(expression);
    return 0;
}

运行结果为

表达式: 5+2*5+(6/3+7*3)+2 #

读取字符: 5
将操作数 5 压入 OPND 栈
OPTR栈: #
OPND栈: 5

读取字符: +
将运算符 '+' 压入 OPTR 栈
OPTR栈: # +
OPND栈: 5

读取字符: 2
将操作数 2 压入 OPND 栈
OPTR栈: # +
OPND栈: 5 2

读取字符: *
将运算符 '*' 压入 OPTR 栈
OPTR栈: # + *
OPND栈: 5 2

读取字符: 5
将操作数 5 压入 OPND 栈
OPTR栈: # + *
OPND栈: 5 2 5

读取字符: +
计算: 2 * 5 = 10
OPTR栈: # +
OPND栈: 5 10
计算: 5 + 10 = 15
OPTR栈: #
OPND栈: 15
将运算符 '+' 压入 OPTR 栈
OPTR栈: # +
OPND栈: 15

读取字符: (
将 '(' 压入 OPTR 栈
OPTR栈: # + (
OPND栈: 15

读取字符: 6
将操作数 6 压入 OPND 栈
OPTR栈: # + (
OPND栈: 15 6

读取字符: /
将运算符 '/' 压入 OPTR 栈
OPTR栈: # + ( /
OPND栈: 15 6

读取字符: 3
将操作数 3 压入 OPND 栈
OPTR栈: # + ( /
OPND栈: 15 6 3

读取字符: +
计算: 6 / 3 = 2
OPTR栈: # + (
OPND栈: 15 2
将运算符 '+' 压入 OPTR 栈
OPTR栈: # + ( +
OPND栈: 15 2

读取字符: 7
将操作数 7 压入 OPND 栈
OPTR栈: # + ( +
OPND栈: 15 2 7

读取字符: *
将运算符 '*' 压入 OPTR 栈
OPTR栈: # + ( + *
OPND栈: 15 2 7

读取字符: 3
将操作数 3 压入 OPND 栈
OPTR栈: # + ( + *
OPND栈: 15 2 7 3

读取字符: )
遇到 ')'，处理括号内的所有运算
计算: 7 * 3 = 21
OPTR栈: # + ( +
OPND栈: 15 2 21
计算: 2 + 21 = 23
OPTR栈: # + (
OPND栈: 15 23
弹出 '('
OPTR栈: # +
OPND栈: 15 23

读取字符: +
计算: 15 + 23 = 38
OPTR栈: #
OPND栈: 38
将运算符 '+' 压入 OPTR 栈
OPTR栈: # +
OPND栈: 38

读取字符: 2
将操作数 2 压入 OPND 栈
OPTR栈: # +
OPND栈: 38 2

读取字符: #
计算: 38 + 2 = 40
OPTR栈: #
OPND栈: 40
将运算符 '#' 压入 OPTR 栈
OPTR栈: # #
OPND栈: 40

最终结果: 40