前言:
先理解原理,再看代码,注意标红字体很重要!结尾附完整测试代码,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;
}
测试截图:文章来源:https://www.toymoban.com/news/detail-753370.html
文章来源地址https://www.toymoban.com/news/detail-753370.html
参考:
- 石田保辉:《我的第一本算法书》
- 渡部有隆:《挑战程序设计竞赛2》
- 程杰:《大话数据结构》
到了这里,关于【数据结构】【栈(stack)应用】四则运算表达式求值(支持括号、负数)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!