【数据结构】【栈（stack）应用】四则运算表达式求值（带括号）

前言：

        先理解原理，再看代码，注意标红字体很重要！结尾附完整测试代码，C语言实现！

更新留言：

        本来是侧重演示栈结构的使用，后面评论区发现很多朋友对这个四则运算比较感兴趣，特此做了更新，新增了对负数的运算支持。

        若您也有新的想法或者需求，请在评论区留言，我将尽可能的实现。需要代码的朋友请直接在章末获取。

        再次感谢您的阅览，谢谢！（更新时间2023年12月05日）

一、四则运算表达式求值

        栈的现实应用也很多，这里重点讲一下比较常见的应用：数学表达式的求值。进入正题之前先讲一下逆波兰的含义。

1.逆波兰（后缀）表达式

        对于“9+(3-1)×3+10÷2”，如果要用后缀表示法应该是什么样子：“9 3 1-3*+102/+”，这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。

        请参考下图熟悉一下逆波兰表达式，不需要纠结。

2.后缀表达式计算结果

        计算机如何应用后缀表达式表示“9+(3-1)×3+10÷2”的：

        后缀表达式：9 3 1-3*+10 2/+

        规则：

• 遍历后缀表达式，如果遇到数字则直接入栈，如果遇到操作符，则弹出栈顶的两个元素，进行计算后将结果入栈。
• 最终，栈内剩余的元素就是整个表达式的计算结果。

图文演示：

1）初始化一个空栈。此栈用来对要运算的数字进出使用。如下图中左图所示。

2）后缀表达式中前三个都是数字，所以9、3、1进栈。如下图中右图所示。

 3）接下来是“-”，所以将栈中的1出栈作为减数，3出栈作为被减数，并运算3-1得到 2，再将2进栈，如下图中左图所示。

4）接着是数字3进栈，如下图中右图所示。 

5）后面是“*”，也就意味着栈中3和2出栈，2与3相乘，得到6，并将6进栈，如下图中左图所示。

6）下面是“+”，所以栈中6和9出栈，9与6相加，得到15，将15进栈，如下图中右图所示。

7）接着是10与2两数字进栈，如下图中左图所示。

8）接下来是符号“/”，因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈，如下图中右图所示。

 9）最后一个是符号“+”，所以15与5出栈并相加，得到20，将20进栈，如下图中左图所示。

10）结果是20出栈，栈变为空，如下图中右图所示。

注：如果对后缀表达式“9 3 1-3+10 2/+”是怎么出来的？这个问题有疑问的。请继续往下看中缀表达式转后缀表达式。

3.中缀表达式转后缀表达式

        我们把平时所用的标准四则运算表达式，即“9+(3-1)×3+10÷2”叫做中缀表达式。因为所有的运算符号都在两数字的中间，现在我们的问题就是中缀到后缀的转化。

        中缀表达式“9+(3-1)×3+10÷2”转化为后缀表达式“9 3 1-3*+10 2/+”

规则：

1. 遇到数字就直接输出到后缀表达式中，遇到操作符就判断其优先级，并将其压入栈中。
2. 如果栈顶元素的优先级大于等于当前操作符，则先将栈顶元素弹出并输出到后缀表达式中，再将当前操作符压入栈中。
3. 如果遇到了左括号，则直接将其压入栈中，如果遇到了右括号，则弹出栈中的元素，直到遇到了左括号为止，并将这些元素输出到后缀表达式中。
4. 最后，将栈中剩余的元素依次弹出，并输出到后缀表达式中。

图文演示：

1）初始化一空栈，用来对符号进出栈使用。如下图的左图所示。

2）第一个字符是数字9，输出9，后面是符号“+”，进栈。如下图的右图所示。

3）第三个字符是“(”，依然是符号，因其只是左括号，还未配对，故进栈。如下图的左图所示。

4）第四个字符是数字3，输出，总表达式为93，接着是“-”，进栈。如下图的右图所示。

5）接下来是数字1，输出，总表达式为 9 31，后面是符号“)”，此时，我们需要去匹配 此前的“(”，所以栈顶依次出栈，并输出，直到“(”出栈为止。此时左括号上方只有“-”， 因此输出“-”。总的输出表达式为 9 3 1-。如下图的左图所示。

6）紧接着是符号“×”，因为此时的栈顶符号为“+”号，优先级低于“×”，因此不输出，“*”进栈。接着是数字3，输出，总的表达式为 9 3 1-3。如下图的右图所示。

7）之后是符号“+”，此时当前栈顶元素“”比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”号更低的优先级，所以全部出栈），总输出表达式为9 3 1-3+。然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“+”是指中缀表达式中开头的9 后面那个“+”，而下图的左图中的栈底（也是栈顶）的“+”是指“9+(3-1)×3+”中的最后 一个“+”。

8）紧接着数字10，输出，总表达式变为9 31-3*+10。后是符号“÷”，所以“/”进栈。如下图的右图所示。

 9）最后一个数字2，输出，总的表达式为9 31-3+10 2。如下图的左图所示。

10）因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为 93 1-3+10 2/+。如下图的右图所示。

        从刚才的推导中你会发现，要想让计算机具有处理我们通常的标准（中缀）表达式的能力，最重要的就是两步：

        1.将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。

        2.将后缀表达式进行运算得出结果（栈用来进出运算的数字）。

        整个过程，都充分利用了栈的后进先出特性来处理，理解好它其实也就理解好了栈这个数据结构。

        接下来就是代码实现了。

4.代码实现

        请务必看懂前面两节的内容，思路和原理往往比代码更重要！！！

代码分三部分：

        1）栈结构的构造（C语言实现）

        2）中缀表达式转化为后缀表达式（栈用来进出运算的符号）

        3）后缀表达式进行运算得出结果（栈用来进出运算的数字）

4.1栈结构构造

typedef struct {
    double* data;  // 数组指针
    int top;  // 栈顶指针
    int size;  // 栈的大小
} Stack;

// 初始化栈
void initStack(Stack* s, int size) {
    s->data = (double*)malloc(sizeof(double) * size);// 动态分配数组内存
    s->top = -1;
    s->size = size;
}

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

// 判断栈是否已满
int isFull(Stack* s) {
    return s->top == s->size - 1;
}

// 入栈
void push(Stack* s, double value) {
    if (isFull(s)) { // 检查栈是否已满
        printf("Stack overflow\n");
        exit(1); // 若栈已满，则退出程序
    }

    s->top++; // 栈顶指针加1
    s->data[s->top] = value; // 在栈顶插入新值
}

// 出栈
double pop(Stack* s) {
    if (isEmpty(s)) { // 检查栈是否为空
        printf("Stack underflow\n");
        exit(1); // 若栈为空，则退出程序
    }

    double value = s->data[s->top]; // 储存栈顶元素的值
    s->top--; // 栈顶指针减1
    return value; // 返回栈顶元素的值
}

// 获取栈顶元素
double top(Stack* s) {
    if (isEmpty(s)) { // 检查栈是否为空
        printf("Stack underflow\n");
        exit(1); // 若栈为空，则退出程序
    }

    return s->data[s->top]; // 返回栈顶元素的值
}

4.2将中缀转换成后缀

// 将中缀表达式转换成后缀表达式
void infixToPostfix(char* infix, char* postfix) {
    Stack s;
    initStack(&s, 100);// 初始化栈

    char* p = infix;// 使用指针遍历中缀表达式
    char* q = postfix;// 使用指针储存后缀表达式
    while (*p != '\0') {// 如果当前位置不为空
        if (isdigit(*p)) {// 如果当前位置是数字
            while (isdigit(*p) || *p == '.') {
                *q = *p;// 直接输出
                q++;
                p++;
            }
            *q = ' ';
            q++;
        }
        else if (*p == '+' || *p == '-' || *p == '*' || *p == '/') {// 如果当前位置是运算符
            int priority1 = getPriority(*p);// 获取当前运算符的优先级
            while (!isEmpty(&s) && isOperator(top(&s)) && getPriority(top(&s)) >= priority1) {
                // 如果栈不空，栈顶为运算符，并且栈顶运算符的优先级大于等于当前运算符的优先级
                char op = pop(&s);// 将栈顶运算符弹出
                *q = op;// 将弹出的运算符输出到后缀表达式中
                q++;
                *q = ' ';// 输出空格
                q++;
            }
            push(&s, *p);// 将当前运算符入栈
            p++;
        }
        else if (*p == '(') {// 如果当前位置是左括号
            push(&s, *p);// 将其入栈
            p++;
        }
        else if (*p == ')') {// 如果当前位置是右括号
            while (!isEmpty(&s) && top(&s) != '(') {// 不断将栈中的元素弹出，直到遇到左括号
                char op = pop(&s);
                *q = op;// 将弹出的运算符输出到后缀表达式中
                q++;
                *q = ' ';// 输出空格
                q++;
            }
            if (!isEmpty(&s) && top(&s) == '(') {// 如果栈不空且栈顶元素是左括号
                pop(&s);// 将左括号弹出并丢弃
            }
            else {
                printf("Invalid expression: %s\n", infix);// 若遍历完中缀表达式后栈中仍然有元素，或遇到错误情况，则输出错误信息
                exit(1);
            }
            p++;
        }
        else {// 如果当前位置不是数字、运算符、左括号或右括号，直接跳过
            p++;
        }
    }

    while (!isEmpty(&s)) {// 如果栈不空，则将栈中所有元素弹出并输出到后缀表达式中
        char op = pop(&s);
        *q = op;
        q++;
        *q = ' ';// 输出空格
        q++;
    }

    *(q - 1) = '\0';// 给后缀表达式添加结束符
}

4.3计算后缀表达式的值

// 计算后缀表达式的值
double evaluate(char* postfix) {
    Stack s;
    initStack(&s, 100);// 初始化栈

    char* p = postfix;// 使用指针遍历后缀表达式
    while (*p != '\0') {// 如果当前位置不为空
        if (isdigit(*p)) {// 如果当前位置是数字
            double num = *p - '0';// 获取数字的整数部分
            p++;
            while (isdigit(*p) || *p == '.') {// 继续读取小数部分
                if (*p == '.') {    // 如果当前位置是小数点
                    p++;
                    double frac = 0.1;// 初始化分数
                    while (isdigit(*p)) {// 继续读取小数部分
                        num += (*p - '0') * frac;// 计算小数值
                        p++;
                        frac /= 10;// 分数部分减小
                    }
                    break;  // 跳出读取小数值的循环
                }
                else {// 如果不是小数点，表示当前位置是数字
                    num = num * 10 + (*p - '0');// 计算数字值
                    p++;
                }
            }
            push(&s, num);// 将数字入栈
        }
        else if (*p == '+' || *p == '-' || *p == '*' || *p == '/') {// 如果当前位置是运算符
            double num2 = pop(&s);// 从栈中弹出栈顶元素作为第二个操作数
            double num1 = pop(&s);// 再从栈中弹出栈顶元素作为第一个操作数
            double result = operate(num1, num2, *p);// 利用operate函数计算出结果
            push(&s, result);// 将结果压入栈中
            p++;
        }
        else {
            p++;
        }
    }

    double value = pop(&s);
    return value;// 返回栈顶元素，即为最终结果
}

完整测试代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

typedef struct {
    double* data;  // 数组指针
    int top;  // 栈顶指针
    int size;  // 栈的大小
} Stack;

// 初始化栈
void initStack(Stack* s, int size) {
    s->data = (double*)malloc(sizeof(double) * size);// 动态分配数组内存
    s->top = -1;
    s->size = size;
}

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

// 判断栈是否已满
int isFull(Stack* s) {
    return s->top == s->size - 1;
}

// 入栈
void push(Stack* s, double value) {
    if (isFull(s)) { // 检查栈是否已满
        printf("Stack overflow\n");
        exit(1); // 若栈已满，则退出程序
    }

    s->top++; // 栈顶指针加1
    s->data[s->top] = value; // 在栈顶插入新值
}

// 出栈
double pop(Stack* s) {
    if (isEmpty(s)) { // 检查栈是否为空
        printf("Stack underflow\n");
        exit(1); // 若栈为空，则退出程序
    }

    double value = s->data[s->top]; // 储存栈顶元素的值
    s->top--; // 栈顶指针减1
    return value; // 返回栈顶元素的值
}

// 获取栈顶元素
double top(Stack* s) {
    if (isEmpty(s)) { // 检查栈是否为空
        printf("Stack underflow\n");
        exit(1); // 若栈为空，则退出程序
    }

    return s->data[s->top]; // 返回栈顶元素的值
}

// 判断是否为运算符
int isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

// 获取运算符优先级
int getPriority(char op) {
    switch (op) {
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    default:
        return 0;
    }
}

// 四则运算
double operate(double num1, double num2, char op) {
    switch (op) {
    case '+':
        return num1 + num2;
    case '-':
        return num1 - num2;
    case '*':
        return num1 * num2;
    case '/':
        return num1 / num2;
    default:
        printf("Invalid operator: %c\n", op);
        exit(1);
    }
}

// 计算后缀表达式的值
double evaluate(char* postfix) {
    Stack s;
    initStack(&s, 100);// 初始化栈

    char* p = postfix;// 使用指针遍历后缀表达式
    while (*p != '\0') {// 如果当前位置不为空
        if (isdigit(*p)) {// 如果当前位置是数字
            double num = *p - '0';// 获取数字的整数部分
            p++;
            while (isdigit(*p) || *p == '.') {// 继续读取小数部分
                if (*p == '.') {    // 如果当前位置是小数点
                    p++;
                    double frac = 0.1;// 初始化分数
                    while (isdigit(*p)) {// 继续读取小数部分
                        num += (*p - '0') * frac;// 计算小数值
                        p++;
                        frac /= 10;// 分数部分减小
                    }
                    break;  // 跳出读取小数值的循环
                }
                else {// 如果不是小数点，表示当前位置是数字
                    num = num * 10 + (*p - '0');// 计算数字值
                    p++;
                }
            }
            push(&s, num);// 将数字入栈
        }
        else if (*p == '+' || *p == '-' || *p == '*' || *p == '/') {// 如果当前位置是运算符
            double num2 = pop(&s);// 从栈中弹出栈顶元素作为第二个操作数
            double num1 = pop(&s);// 再从栈中弹出栈顶元素作为第一个操作数
            double result = operate(num1, num2, *p);// 利用operate函数计算出结果
            push(&s, result);// 将结果压入栈中
            p++;
        }
        else {
            p++;
        }
    }

    double value = pop(&s);
    return value;// 返回栈顶元素，即为最终结果
}

// 将中缀表达式转换成后缀表达式
void infixToPostfix(char* infix, char* postfix) {
    Stack s;
    initStack(&s, 100);// 初始化栈

    char* p = infix;// 使用指针遍历中缀表达式
    char* q = postfix;// 使用指针储存后缀表达式
    while (*p != '\0') {// 如果当前位置不为空
        if (isdigit(*p)) {// 如果当前位置是数字
            while (isdigit(*p) || *p == '.') {
                *q = *p;// 直接输出
                q++;
                p++;
            }
            *q = ' ';
            q++;
        }
        else if (*p == '+' || *p == '-' || *p == '*' || *p == '/') {// 如果当前位置是运算符
            int priority1 = getPriority(*p);// 获取当前运算符的优先级
            while (!isEmpty(&s) && isOperator(top(&s)) && getPriority(top(&s)) >= priority1) {
                // 如果栈不空，栈顶为运算符，并且栈顶运算符的优先级大于等于当前运算符的优先级
                char op = pop(&s);// 将栈顶运算符弹出
                *q = op;// 将弹出的运算符输出到后缀表达式中
                q++;
                *q = ' ';// 输出空格
                q++;
            }
            push(&s, *p);// 将当前运算符入栈
            p++;
        }
        else if (*p == '(') {// 如果当前位置是左括号
            push(&s, *p);// 将其入栈
            p++;
        }
        else if (*p == ')') {// 如果当前位置是右括号
            while (!isEmpty(&s) && top(&s) != '(') {// 不断将栈中的元素弹出，直到遇到左括号
                char op = pop(&s);
                *q = op;// 将弹出的运算符输出到后缀表达式中
                q++;
                *q = ' ';// 输出空格
                q++;
            }
            if (!isEmpty(&s) && top(&s) == '(') {// 如果栈不空且栈顶元素是左括号
                pop(&s);// 将左括号弹出并丢弃
            }
            else {
                printf("Invalid expression: %s\n", infix);// 若遍历完中缀表达式后栈中仍然有元素，或遇到错误情况，则输出错误信息
                exit(1);
            }
            p++;
        }
        else {// 如果当前位置不是数字、运算符、左括号或右括号，直接跳过
            p++;
        }
    }

    while (!isEmpty(&s)) {// 如果栈不空，则将栈中所有元素弹出并输出到后缀表达式中
        char op = pop(&s);
        *q = op;
        q++;
        *q = ' ';// 输出空格
        q++;
    }

    *(q - 1) = '\0';// 给后缀表达式添加结束符
}


int main() {
    char infix[100];
    char postfix[100];

    printf("Enter an infix expression: ");
    scanf("%s", infix);

    infixToPostfix(infix, postfix);// 将中缀表达式转为后缀表达式
    printf("Postfix notation: %s\n", postfix);

    double result = evaluate(postfix);// 计算后缀表达式的值
    printf("Result: %g\n", result);

    return 0;
}

测试结果： 

更新测试代码： 支持负数运算

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

typedef struct {
    double* data;  // 存储栈数据的数组指针
    int top;       // 栈顶指针
    int size;      // 栈的大小
} Stack;

// 初始化栈
void initStack(Stack* s, int size) {
    s->data = (double*)malloc(sizeof(double) * size); // 动态分配内存
    s->top = -1; // 初始化栈顶指针
    s->size = size; // 设置栈的大小
}

// 判断栈是否为空
int isEmpty(Stack* s) {
    return s->top == -1; // 栈顶指针为-1时，栈为空
}

// 判断栈是否已满
int isFull(Stack* s) {
    return s->top == s->size - 1; // 栈顶指针等于栈的大小减1时，栈已满
}

// 入栈操作
void push(Stack* s, double value) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        exit(1); // 栈满时退出程序
    }
    s->top++; // 栈顶指针增加
    s->data[s->top] = value; // 将值放入栈顶
}

// 出栈操作
double pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        exit(1); // 栈空时退出程序
    }
    double value = s->data[s->top]; // 取栈顶元素
    s->top--; // 栈顶指针减少
    return value; // 返回栈顶元素
}

// 获取栈顶元素
double top(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        exit(1); // 栈空时退出程序
    }
    return s->data[s->top]; // 返回栈顶元素
}

// 判断字符是否是运算符
int isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

// 获取运算符优先级
int getPriority(char op) {
    switch (op) {
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    default:
        return 0;
    }
}

// 执行四则运算
double operate(double num1, double num2, char op) {
    switch (op) {
    case '+':
        return num1 + num2;
    case '-':
        return num1 - num2;
    case '*':
        return num1 * num2;
    case '/':
        return num1 / num2;
    default:
        printf("Invalid operator: %c\n", op);
        exit(1); // 遇到无效运算符时退出程序
    }
}

// 判断是否是负号
int isNegativeSign(char* p, char* infix) {
    if (*p != '-') return 0; // 如果不是减号，则返回0
    if (p == infix) return 1; // 如果是表达式的开始，则是负号
    // 如果前一个字符是左括号或其他运算符，则当前的减号是负号
    return (*(p - 1) == '(') || isOperator(*(p - 1));
}

// 将中缀表达式转换为后缀表达式
void infixToPostfix(char* infix, char* postfix) {
    Stack s;
    initStack(&s, 100); // 初始化栈

    char* p = infix;
    char* q = postfix;
    while (*p != '\0') {
        if (isdigit(*p)) { // 如果是数字
            do {
                *q++ = *p++;
            } while (isdigit(*p) || *p == '.');
            *q++ = ' ';
        } else if (isOperator(*p)) {
            if (*p == '-' && isNegativeSign(p, infix)) {
                *q++ = '0'; // 补零以处理负号
                *q++ = ' ';
            }
            while (!isEmpty(&s) && isOperator(top(&s)) &&
                   getPriority(top(&s)) >= getPriority(*p)) {
                *q++ = pop(&s);
                *q++ = ' ';
            }
            push(&s, *p);
            p++;
        } else if (*p == '(') {
            push(&s, *p); // 处理左括号
            p++;
        } else if (*p == ')') {
            while (!isEmpty(&s) && top(&s) != '(') {
                *q++ = pop(&s); // 处理右括号
                *q++ = ' ';
            }
            if (!isEmpty(&s)) {
                pop(&s); // 弹出左括号
            }
            p++;
        } else {
            p++; // 跳过空格
        }
    }

    while (!isEmpty(&s)) { // 将栈中剩余的运算符加入后缀表达式
        *q++ = pop(&s);
        *q++ = ' ';
    }

    *q = '\0'; // 结束后缀表达式
}

// 计算后缀表达式的值
double evaluate(char* postfix) {
    Stack s;
    initStack(&s, 100); // 初始化栈

    char* p = postfix;
    while (*p != '\0') {
        if (isdigit(*p)) { // 如果是数字
            double num = 0.0;
            while (isdigit(*p)) { // 提取整数部分
                num = num * 10 + (*p - '0');
                p++;
            }
            if (*p == '.') { // 提取小数部分
                double frac = 0.1;
                p++;
                while (isdigit(*p)) {
                    num += (*p - '0') * frac;
                    frac /= 10;
                    p++;
                }
            }
            push(&s, num);
        } else if (*p == ' ') {
            p++;
        } else if (isOperator(*p)) { // 如果是运算符
            double num2 = pop(&s);
            double num1 = pop(&s);
            double result = operate(num1, num2, *p);
            push(&s, result);
            p++;
        }
    }

    return pop(&s); // 返回计算结果
}

int main() {
    char infix[100];
    char postfix[100];

    printf("Enter an infix expression: ");
    scanf("%s", infix); // 读取中缀表达式

    infixToPostfix(infix, postfix); // 将中缀表达式转换为后缀表达式
    printf("Postfix notation: %s\n", postfix); // 打印后缀表达式

    double result = evaluate(postfix); // 计算后缀表达式的结果
    printf("Result: %g\n", result); // 打印结果

    return 0;
}

 测试截图：

文章来源地址https://www.toymoban.com/news/detail-713632.html

参考：

1. 石田保辉：《我的第一本算法书》
2. 渡部有隆：《挑战程序设计竞赛2》
3. 程杰：《大话数据结构》

到了这里，关于【数据结构】【栈（stack）应用】四则运算表达式求值（带括号）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！