数据结构之栈的应用（算术计算）

超、凢脫俗 2022-05-31 04:41 206阅读 0赞

**栈的应用实战2-->算术计算**

问题的提出：计算机的本质工作就是做数学运算，那计算机可以读入字符串“9 + (3 - 1) \* 5 + 8 / 2”并计算值吗？

波兰科学家在20世纪50年代提出了一种将运算符放在数字后面的后缀表达式。对应的，我们习惯的数学表达式叫做中缀表达式。

由于中缀表达式符合人类的阅读和思维习惯，后缀表达式符合计算机的“运算习惯”，所以为了计算机能够读入字符串并计算出数值，我们需要将中缀表达式转换成后缀表达式。

那么问题就出现了，如何将中缀表达式转换成后缀表达式？

实例：  
5 + 3 => 5 3 +  
1 + 2 \* 3 => 1 2 3 \* +  
9 + ( 3 – 1 ) \* 5 => 9 3 1 – 5 \* +

当然了，办法总比问题多，就这样，中缀表达式转换成后缀表达式的算法就应运而生了。

解决方案：  
1.遍历中缀表达式中的数字和符号；  
1.1.对于数字：直接输出；  
1.2.对于符号；  
1.2.1.左括号：进栈；  
1.2.2.符号：与栈顶符号进行优先级比较；  
1.2.2.1.栈顶符号优先级低：即比栈顶符号优先级高，进栈；  
1.2.2.2.栈顶符号优先级不低：即比栈顶符号优先级低，  
将栈顶符号弹出并输出，之后进栈；  
1.2.3.右括号：将栈顶符号弹出并输出，直到匹配左括号。  
2.遍历结束：将栈中的所有符号弹出并输出。

算法框架：

![SouthEast][]

实现代码下载地址：http://download.csdn.net/download/u014754841/10244007

这里只是实现了中缀表达式转换成后缀表达式转换，计算机算术计算还没真正开始，计算机是如何基于后缀表达式计算的？

计算机对后缀表达式的运算是基于栈的，所以我们还得为计算机的计算再创建一个栈。

**计算机基于后缀表达式计算的解决方案**

1.遍历后缀表达式中的数字和符号  
1.1.对于数字：进栈；  
1.2.对于符号：  
1.2.1.从栈中弹出右操作数；  
1.2.2.从栈中弹出左操作数；

1.2.3.根据符号进行运算；  
1.2.4.将运算结果压入栈中。

2.遍历结束：栈中的唯一数字为计算结果。

**算法框架**

![SouthEast 1][]

后缀计算实现代码下载地址：http://download.csdn.net/download/u014754841/10244015

再次唠叨一下，作个总结：

1.中缀表达式是人习惯的表达方式。  
2.后缀表达式是计算机喜欢的表达方式。  
3.通过栈可以方便的将中缀形式变换为后缀形式。  
4.中缀表达式的计算过程类似程序编译运行的过程。

到此，虽有中缀表达式转换成后缀表达式的代码，也有后缀表达式计算的代码，但是离输入算术表达式到计算出结果还有一定的路程需要去趟。要想实现算术计算，还需将这两个算法糅合到一起才可。详请见实例代码。

整体代码下载地址：http://download.csdn.net/download/u014754841/10244031

控制台小程序下载地址：http://download.csdn.net/download/u014754841/10244045

[SouthEast]: /images/20220531/41595cffaa134c80ab194f921e840a28.png
[SouthEast 1]: /images/20220531/91297d7912e64752a431c4720e57d336.png

发表评论取消回复

表情：

评论列表（有 0 条评论，206人围观）

还没有评论，来说两句吧...

相关阅读

相关 C++版数据结构之栈的应用

**1.概念** ** 栈（stack）是存放数据对象的一种特殊容器，其中的数据元素按线性的逻辑次序排列，故也可定义首、末元素。** ** ...

秒速五厘米/ 2024年04月18日 23:17/ 0 赞/ 60 阅读

相关数据结构：栈及其应用

栈的初步认识栈的设计 Stack接口 ArrayStack类(栈的顺序存储具体实现) 十进制和十六进制的互相转换

红太狼/ 2023年09月28日 05:09/ 0 赞/ 20 阅读

相关数据结构-栈应用（中缀转后缀并计算结果）

关于中缀和后缀表达式基础概念自行百度。 > 对于中缀转后缀表达式并计算结果思路可归纳为以下： > > 1、将每个数据当做一个结构体，包含对应的类型以及数值; >

向右看齐/ 2022年06月03日 04:51/ 0 赞/ 115 阅读

相关数据结构之栈的应用（算术计算）

栈的应用实战2-->算术计算问题的提出：计算机的本质工作就是做数学运算，那计算机可以读入字符串“9 + (3 - 1) \ 5 + 8 / 2”并计算值吗？波兰科学家在

超、凢脫俗/ 2022年05月31日 04:41/ 0 赞/ 207 阅读

相关数据结构之栈的应用(语法匹配)

栈的应用实战1-->语法匹配问题的提出：在C语言中有一些符号是成对匹配出现的，如： 1.括号: ( ), \[ \], \{ \}, <>； 2. 引号: ‘ ‘, “

Myth丶恋晨/ 2022年05月31日 03:17/ 0 赞/ 185 阅读

相关数据结构之栈在LeetCode的应用

临近找工作，在牛客网上看了很多面筋发现自己是在菜的不行，所以前期时间春招也没有参加（只是象征性的投了几个建立，却都石沉大海）深知自己的不足。“打铁还需自身硬”，所以在网上找了一

- 日理万妓/ 2022年05月25日 07:26/ 0 赞/ 188 阅读

相关数据结构_栈及其应用

栈及其应用栈栈是存放数据对象的一种特殊容器，栈中的元素始终遵循后进先出的顺序，作为一种抽象数据类型，栈支持的操作接口如下： stack<T> S;

爱被打了一巴掌/ 2022年05月23日 05:58/ 0 赞/ 250 阅读

相关数据结构之栈

什么是栈从栈的操作特性上来看，栈是一种 “操作受限”的线性表，只允许在一端插入和删除数据，且满足先进后出、后进先出的特性。实现一个栈栈可以用数组或链表来实现

Bertha 。/ 2022年05月16日 14:29/ 0 赞/ 232 阅读

相关（数据结构实验）栈的应用－算术表达式求值

实验目的： 1．掌握栈的定义及实现； 2．掌握利用栈求解算术表达式的方法。实验内容：通过修改完善教材中的算法3.22，利用栈来实现算术表达式求值的算法

短命女/ 2022年04月14日 04:42/ 0 赞/ 752 阅读

相关数据结构：栈的应用

括号匹配： ![20190719132106415.png][] 从上面这个图中我么可以看出，我们平时用的括号是怎么样的，我么都知道，括号一定是两两配对的。有开必有合，

以你之姓@/ 2021年12月04日 01:13/ 0 赞/ 328 阅读