龙空技术网

栈的应用之四则运算

自强不息20200820 83

前言:

今天我们对“出栈结果”可能比较讲究,姐妹们都需要学习一些“出栈结果”的相关文章。那么小编也在网摘上汇集了一些有关“出栈结果””的相关文章,希望小伙伴们能喜欢,兄弟们一起来学习一下吧!

一 四则运算表达式求值

采用后缀(逆波兰)表示法

表达式:9+(3-1)x3+10÷2

流程:

1 上面的表达式为中缀表达式,我们需要先转换成后缀表达式,转换过程如下:

1.1 初始化一个空栈,用来对符号进出栈使用。

1.2 第一个字符是数字9,输出9,后面符号是“+”,进栈。

1.3 第三个字符是“(”,因其未配对,进栈。

1.4 第四个符号是数字3,输出3,总表达式为9 3,接着是“-”,进栈,接着是数字1,总表达式为9 3 1.

1.5 接下来的字符是“)”,此时我们需要去匹配此前的“(”,所以栈顶依次出栈,并输出,直到“(”出栈。

此时左括号上方只有“-”,因此输出“-”,总的输出表达式为 ” 9 3 1 - “ 如上图。

接着是符号“ x ",因为此时的栈顶符号为“+”号,优先级低于“x”,因此不输出,“x"进栈,接着是数字3,输出。如下图所示:

图 1.6

接下来是符号”+“,此时当前栈顶元素”x" 比这个 “+”优先级高,因此栈中元素出栈并输出(没有比“+”号更低的优先级,所以全部出栈),总输出表达式为 “9 3 1 - 3 * +”。然后将当前这个符号“+”进栈。如下图所示:

图1.7

接下来是是数字10,输出,总表达式为”9 3 1 - 3 * + 10“。后是符号”÷“,进栈。如下图所示:

图1.8

最后一个数字2,输出,总表达式为 ”9 3 1 - 3 * + 10 2“

因已经到最后,所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为” 9 3 1 - 3 * + 10 2 ÷ + “

2 后缀表达式计算结果

后缀表达式:9 3 1 - 3 * + 10 2 ÷ +

规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。

2.1 初始化一个空栈

2.2 后缀表达式中前三个都是数字,所以 9 3 1 进栈,如图2.1

图2.1

2.3 接下来是”-“,将栈中1出栈作为减数,3出栈作为被减数,并运算3-1得到2,再将2进栈,如图2.2

图2.2

2.4 接着是数字3,进栈,如图2.3所示

图2.3

2.5 接着是符号”*“,出栈3 和 2, 并运算2*3得6,入栈6,如图2.4所示

图2.4

2.6 接着是符号”+“,出栈6和9,运算6+19得15,入栈15,如图2.5所示

图2.5

2.7 接着是数字 10 和 2,入栈 10 和 2,如图 2.6所示

图2.6

2.8 接着是符号”÷“,出栈2作为除数,出栈10作为被除数,运算10÷2得5,入栈5,如图2.7所示

图2.7

2.9 最后是符号”+“,出栈5和15,运算5+15得20,入栈20.如图2.8所示

图2.8

2.10 结果是20出栈,栈变为空。

标签: #出栈结果 #利用栈计算表达式 42411321 #栈的运算操作规则