前言：
先理解原理，再看代码，注意标红字体很重要！结尾附完整测试代码，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）第一个字符是数字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;
}测试截图：
参考：
- 石田保辉：《我的第一本算法书》
- 渡部有隆：《挑战程序设计竞赛2》
- 程杰：《大话数据结构》
文章出处登录后可见！
已经登录？立即刷新
