深入理解算数表达式求值：后缀表达式的转换与计算

🕗 发布于 2024-07-25 09:15 数据结构

归纳编程学习的感悟，
记录奋斗路上的点滴，
希望能帮到一样刻苦的你！
如有不足欢迎指正！
共同学习交流！
🌎欢迎各位→点赞 👍+ 收藏⭐ + 留言📝
没人会嘲笑竭尽全力的人！

前言

在计算机科学中，算数表达式的求值是一个经典的问题，尤其是在编译器设计和计算器应用中。中缀表达式，即我们日常所见的数学表达式（如 3 + 4 或 (2 + 3) * 4），虽然直观易懂，但对于计算机来说并不友好，因为它们需要遵循特定的运算优先级规则。因此，将中缀表达式转换为后缀表达式（也称为逆波兰记法或RPN）可以简化计算过程，使计算机能够更有效地进行求值。

后缀表达式简介

后缀表达式的特点是运算符紧跟在其操作数之后，例如，中缀表达式 3 + 4 转换为后缀表达式后成为 3 4 +。这种格式消除了对运算符优先级的依赖，也不需要使用括号来表示运算的顺序，这使得计算变得更为直接和高效。

中缀到后缀的转换

步骤概述

初始化：创建一个空的运算符栈和一个空的数组。
遍历输入：逐个检查中缀表达式中的每个字符。
- 如果是操作数，直接将其添加到数组。
- 如果是运算符，根据栈顶运算符的优先级与当前运算符比较：
  - 若当前运算符优先级高于栈顶运算符，则将当前运算符压入栈。
  - 若当前运算符优先级低于或等于栈顶运算符，从栈中弹出运算符并添加到数组，直到栈顶运算符优先级低于当前运算符，再将当前运算符压入栈。
- 如果是左括号 (，直接压入栈。
- 如果是右括号 )，则不断从栈中弹出运算符并添加到数组，直到遇到对应的左括号，然后将这对括号丢弃。
处理剩余运算符：当所有字符被处理后，将栈中剩余的运算符依次弹出并添加到数组。

后缀表达式的计算

计算后缀表达式相对直接，主要步骤如下：

初始化：创建一个空的数值栈。
遍历后缀表达式：逐个检查后缀表达式中的每个元素。
- 如果是操作数，将其压入数值栈。
- 如果是运算符，从数值栈中弹出两个操作数，执行相应的运算，然后将结果压回栈中。
最终结果：当所有元素被处理后，数值栈的顶部元素就是整个表达式的计算结果。

示例

假设我们要计算中缀表达式 (3 + 4) * 5 的值，我们首先将其转换为后缀表达式：

初始化：[]（运算符栈） []（输出队列）
遍历：
- (: 压栈 [(]
- 3: 输出 [3]
- +: 压栈 [( +]
- 4: 输出 [3 4]
- ): 弹出 + 并输出 [3 4 +]
- *: 压栈 [ *]
- 5: 输出 [3 4 + 5]
- EOL: 弹出 * 并输出 [3 4 + 5 *]
结果：3 4 + 5 *

接下来，我们计算这个后缀表达式：

初始化：[]（数值栈）
遍历：
- 3: 压栈 [3]
- 4: 压栈 [3 4]
- +: 弹出 4 和 3，计算 3 + 4 = 7，压栈 [7]
- 5: 压栈 [7 5]
- *: 弹出 5 和 7，计算 7 * 5 = 35，压栈 [35]
结果：35

因此，中缀表达式 (3 + 4) * 5 的值为 35。

结论

后缀表达式的转换和计算提供了一种高效且无歧义的方式来处理算数表达式。这种方法不仅在理论上有趣，在实际应用中也非常实用，特别是在需要快速准确地计算表达式的场景中。

下面是我的代码部分

中缀转后缀利用的链栈，所以先加入链栈头文件。

LinkStack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>

typedef char DataType;

typedef struct LStackNode
{
DataType data;
struct LStackNode* next;
}LStackNode,*LinkStack;

void InitLinkStack(LinkStack* top);

int StackEmpty(LinkStack top);

int PushStack(LinkStack top, DataType e);

int PopStack(LinkStack top, DataType* e);

int GetTop(LinkStack top, DataType* e);

int StackLength(LinkStack top);

void DestoryStack(LinkStack top);

LinkStack.cpp

#include "LinkStack.h"
#define _CRT_SECURE_NO_WARNINGS 1

void InitLinkStack(LinkStack* top)
{
*top = (LinkStack)malloc(sizeof(LStackNode));
(*top)->next = NULL;//将链栈头结点指针域置为空
}

int StackEmpty(LinkStack top)
{//判断链栈是否为空
if (top->next == NULL)
{
return 1;
}
else
{
return 0;
}
}

int PushStack(LinkStack top, DataType e)
{//将元素e入栈，入栈成功返回1
LStackNode* p;
p = (LStackNode*)malloc(sizeof(LStackNode));
p->data = e;
p->next = top->next;
top->next = p;
return 1;
}

int PopStack(LinkStack top, DataType* e)
{//将栈顶元素出栈
LStackNode* p;
p = top->next;
if (!p)
{
printf("栈已空\n");
return 0;
}
*e = p->data;
top->next = p->next;
free(p);
return 1;
}

int GetTop(LinkStack top, DataType* e)
{//取栈顶元素
LStackNode* p;
p = top->next;
if (!p)
{
printf("栈已空\n");
return 0;
}
*e = p->data;
return 1;
}

int StackLength(LinkStack top)
{//求链栈长度
LStackNode* p;
int count = 0;
p = top;
while (p->next)
{
p = p->next;
count++;
}
return count;
}

void DestoryStack(LinkStack top)
{//销毁链栈
LStackNode* p, * q;
p = top;
while (!p)
{
q = p;
p = p->next;
free(q);
}
}

主函数

#define _CRT_SECURE_NO_WARNINGS 1
#include"LinkStack.h"
#include<stdio.h>

constexpr auto MaxSize = 50;;

typedef struct
{
float data[MaxSize];
int top;
}SeqStack;

void TranslateExpress(char str[], char exp[]);
float ComputeExpress(char exp[]);

int main()
{
char a[MaxSize], b[MaxSize];
float f;
printf("请输入一个算数表达式：\n");
gets_s(a);
printf("中缀表达式为：%s\n", a);
TranslateExpress(a,b);
printf("后缀表达式为：%s\n",b);
f = ComputeExpress(b);
printf("计算结果：%.0f\n", f);
return 0;
}

void TranslateExpress(char str[], char exp[])
{//中缀表达式转后缀表达式
LinkStack S;//定义一个栈，用于存放运算符
InitLinkStack(&S);
char ch;
char e;
int i = 0, j = 0;
ch = str[i];
i++;
while (ch != '\0')//依次扫描中缀表达式中的每个字符
{
switch (ch)
{
case '('://如果当前字符是左括号，则将其入栈
PushStack(S, ch);
break;
case ')'://如果是右括号，则将栈中的运算符出栈，并将其存入数组exp中
while (GetTop(S, &e) && e != '(')
{
PopStack(S, &e);
exp[j] = e;
j++;
exp[j] = ' ';
j++;
}
PopStack(S, &e);//将左括号出栈
break;
case '+'://如果遇到+和-，因为其优先级低于栈顶运算符的优先级，
case '-'://所以先将栈顶运算符出栈，并将其存入数组exp中，然后将当前运算符入栈
while (!StackEmpty(S) && GetTop(S, &e) && e != '(')
{
PopStack(S, &e);
exp[j] = e;
j++;
exp[j] = ' ';
j++;
}
PushStack(S, ch);//将当前运算符入栈
break;
case '*'://如果遇到的是*和/，则先将同级运算符出栈，并存入数组exp中，
case '/'://然后将当前运算符出栈
while (!StackEmpty(S) && GetTop(S, &e) && e == '/' || e == '*')
{
PopStack(S, &e);
exp[j] = e;
j++;
exp[j] = ' ';
j++;
}
PushStack(S, ch);//当前运算符入栈
break;
case ' '://如果遇到空格，忽略
break;
default://如果遇到操作数，则将操作数直接送入数组exp中，并在
    //其后添加一个空格，用来分割数字字符
while (ch >= '0' && ch <= '9')
{
exp[j] = ch;
j++;
ch = str[i];
i++;
}
i--;
exp[j] = ' ';
j++;
break;
}
ch = str[i];//读入下一个字符，准备处理
i++;
}
while (!StackEmpty(S))//将栈中所有剩余的运算符出栈，送入数组exp中
{
PopStack(S, &e);
exp[j] = e;
j++;
exp[j] = ' ';
j++;
}
exp[j]='\0';
}



float ComputeExpress(char exp[])
{//计算后缀表达式的值
SeqStack S;//利用顺序栈存储浮点型数据，从而防止与链栈中存储的
S.top = -1;//字符数据冲突，利用C++中的模板能更好的解决这一点
int i = 0, value;
float x1, x2;
float result;
while (exp[i] != '\0')
{
if (exp[i] != ' ' && exp[i] >= '0' && exp[i] <= '9')
{//如果当前字符是数字字符
value = 0;
while (exp[i] != ' ')
{
value = value * 10 + exp[i] - '0';
i++;
}
S.top++;
S.data[S.top] = value;//处理之后将数字入栈
}
else//如果当前字符是运算符
{
switch (exp[i])
{//将栈中的数字出栈两次，然后用当前的运算符进行运算，再将结果入栈
case '+':
x1 = S.data[S.top];
S.top--;
x2 = S.data[S.top];
S.top--;
result = x2 + x1;
S.top++;
S.data[S.top] = result;
break;
case '-':
x1 = S.data[S.top];
S.top--;
x2 = S.data[S.top];
S.top--;
result = x2 - x1;
S.top++;
S.data[S.top] = result;
break;
case '*':
x1 = S.data[S.top];
S.top--;
x2 = S.data[S.top];
S.top--;
result = x2 * x1;
S.top++;
S.data[S.top] = result;
break;
case '/':
x1 = S.data[S.top];
S.top--;
x2 = S.data[S.top];
S.top--;
result = x2 / x1;
S.top++;
S.data[S.top] = result;
break;
}
i++;
}
}
result = S.data[S.top];
S.top--;
if (S.top == -1)//如果栈不为空，则将结果出栈，并返回
{
return result;
}
else
{
printf("表达式错误\n");
exit(-1);
}
}

反思总结：

当时写的时候看着参考书的代码一直有个疑问，为什么中缀转后缀用的链栈，而计算后缀的时候用的顺序栈，为什么不能直接都用链栈呢，通过一番折腾，我知道了，因为我的参考书是一本C语言的数据结构，在LinkStack.h里面我规定了DataType是char类型，中缀转后缀，链栈里面存储的是char类型，但是要是计算后缀的话就不能再调用链栈这个数据结构了，因为计算后缀要将数值入栈，是float类型，此时由于我写的链栈只能存储char类型而导致编译器报错，解决这个问题我查阅资料找到了多种办法：一，由于C语言的限制，我可以再写一个存储数值的链栈数据结构，这样较麻烦，得重写链栈操作文件；二，可以利用指针函数，这个又要大幅度改动我的LinkStack.cpp文件里面的函数传参部分，我也没选这种方法；三，可以在main函数里面利用另一种数据结构顺序栈，这是我觉得更方便的办法，虽然会导致部分内存空间的浪费，但只需要简单的改动栈顶指针进行入栈和出栈操作即可。

另外，如果是C++语言将更好的解决这一问题，C++引入了模板，可以在一个程序里利用存储不同数据类型的数据结构，我对模板的应用不太深入，C++是大一上学期自学的，现在已经忘了大部分，所以返回去深入学习的一下模板的应用，针对本题在C++中直接定义LinkStack<char> charStack和LinkStack<float> floatStack可以完美的解决这一问题。

希望这篇博客能帮助你更好地理解后缀表达式的转换和计算过程，以及它在算数表达式求值中的重要性。如果你有任何疑问或需要进一步的解释，请随时提问！

原文地址：https://blog.csdn.net/2301_80585598/article/details/140674576

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：快速入门Jupyter notebook
下一篇：【北京迅为】《i.MX8MM嵌入式Linux开发指南》-第三篇嵌入式Linux驱动开发篇-第五十一章添加设备树节点

配置cobbler服务提供centos7安装源
由RedHat公司基于python语言开发，作用：快速批量部署Linux系统。
阅读更多2024-09-17
【MySQL学习】基础指令全解：构建你的数据库技能
本文详细介绍了SQL操作指令的各种基础和高级操作，帮助读者掌握SQL数据库技巧。
阅读更多2024-09-17
OpenGL笔记二十一之几何类设计
— 2024-09-16 下午。
阅读更多2024-09-17
UiBot教程：实现复杂流程图的高效方法
我们需要在两个流程块之间传递“字符串格式的系统时间”，所以最简单的方法就是在流程图中定义一个变量。举个例子，我们可以创建一个名为x的流程图变量，这样在流程图所包含的所有流程块中都可以直接使用这个变量。
阅读更多2024-09-17
12 数组——27. 移除元素 ★
给你一个数组nums和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。
阅读更多2024-09-17
工资重回“3000块”时代
3000元是一个心理价位，但实际上对于许多家庭来说，可能在县城生活，除了基本的生活开销，很难剩下更多的钱。也就是说，如果你的工作收入在这个“五千块定律”所设定的范围内，并且在三年内没有超过平均水平的涨
阅读更多2024-09-17
谷歌向安卓用户推出Gemini Live聊天机器人
即使你的手机处于锁定状态，屏幕处于关闭状态，你也可以开始与助手交谈，而且还可以通过谷歌(Google)的新款Pixel Buds Pro 2无线耳机进行访问，这样你就可以在手机放在包里的时候免提通话。
阅读更多2024-09-17
Linux进阶命令-sed&split
sed（Stream Editor）是一个流编辑器，用于在文本流中进行文本替换和转换操作。它通常用于命令行环境下，可以接受标准输入（stdin）、文件内容或管道输入，并对文本进行修改或处理。
阅读更多2024-09-17
RTMP直播播放器的几种选择
在选择RTMP直播播放器时，需要根据具体的应用场景、平台兼容性、功能需求以及用户体验等因素进行综合考虑。同时，也可以参考其他用户的评价和专业评测来选择最适合的播放器。
阅读更多2024-09-17
Linux套接字
套接字是实现网络通信的核心组件，它提供了灵活且强大的接口，使得开发者能够轻松地在网络环境中构建复杂的应用程序。无论是TCP还是UDP协议，都可以通过适当的套接字类型来满足不同的通信需求.
阅读更多2024-09-17