前缀、中缀、后缀表达式

转至: 前缀、中缀、后缀表达式

它们都是对表达式的记法,因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与操作数的位置不同:前缀表达式的运算符位于与其相关的操作数之前;中缀和后缀同理。 举例: (3 + 4) × 5 - 6 就是中缀表达式 - × + 3 4 5 6 前缀表达式 3 4 + 5 × 6 - 后缀表达式 中缀表达式(中缀记法) 中缀表达式是一种通用的算术或逻辑公式表示方法,操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。 虽然人的大脑很容易理解与分析中缀表达式,但对计算机来说中缀表达式却是很复杂的,因此计算表达式的值时,通常需要先将中缀表达式转换为前缀或后缀表达式,然后再进行求值。对计算机来说,计算前缀或后缀表达式的值非常简单。 前缀表达式(前缀记法、波兰式) 前缀表达式的运算符位于操作数之前。 前缀表达式的计算机求值: 从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 op 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。 例如前缀表达式“- × + 3 4 5 6”: (1) 从右至左扫描,将6、5、4、3压入堆栈; (2) 遇到+运算符,因此弹出3和4(3为栈顶元素,4为次顶元素,注意与后缀表达式做比较),计算出3+4的值,得7,再将7入栈; (3) 接下来是×运算符,因此弹出7和5,计算出7×5=35,将35入栈; (4) 最后是-运算符,计算出35-6的值,即29,由此得出最终结果。 可以看出,用计算机计算前缀表达式的值是很容易的。 将中缀表达式转换为前缀表达式: 遵循以下步骤: (1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2; (2) 从右至左扫描中缀表达式; (3) 遇到操作数时,将其压入S2; (4) 遇到运算符时,比较其与S1栈顶运算符的优先级: (4-1) 如果S1为空,或栈顶运算符为右括号“)”,则直接将此运算符入栈; (4-2) 否则,若优先级比栈顶运算符的较高或相等,也将运算符压入S1; (4-3) 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较; (5) 遇到括号时: (5-1) 如果是右括号“)”,则直接压入S1; (5-2) 如果是左括号“(”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到右括号为止,此时将这一对括号丢弃; (6) 重复步骤(2)至(5),直到表达式的最左边; (7) 将S1中剩余的运算符依次弹出并压入S2; (8) 依次弹出S2中的元素并输出,结果即为中缀表达式对应的前缀表达式。 例如,将中缀表达式“1+((2+3)×4)-5”转换为前缀表达式的过程如下:

扫描到的元素

S2(栈底->栈顶)

S1 (栈底->栈顶)

说明

5

5

数字,直接入栈

-

5

-

S1为空,运算符直接入栈

)

5

- )

右括号直接入栈

4

5 4

- )

数字直接入栈

×

5 4

- ) ×

S1栈顶是右括号,直接入栈

)

5 4

- ) × )

右括号直接入栈

3

5 4 3

- ) × )

数字

+

5 4 3

- ) × ) +

S1栈顶是右括号,直接入栈

2

5 4 3 2

- ) × ) +

数字

(

5 4 3 2 +

- ) ×

左括号,弹出运算符直至遇到右括号

(

5 4 3 2 + ×

-

同上

+

5 4 3 2 + ×

- +

优先级与-相同,入栈

1

5 4 3 2 + × 1

- +

数字

到达最左端

5 4 3 2 + × 1 + -

S1中剩余的运算符

因此结果为“- + 1 × + 2 3 4 5”。 后缀表达式(后缀记法、逆波兰式) 后缀表达式与前缀表达式类似,只是运算符位于操作数之后。 后缀表达式的计算机求值: 与前缀表达式类似,只是顺序是从左至右: 从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 op 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。 例如后缀表达式“3 4 + 5 × 6 -”: (1) 从左至右扫描,将3和4压入堆栈; (2) 遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素,注意与前缀表达式做比较),计算出3+4的值,得7,再将7入栈; (3) 将5入栈; (4) 接下来是×运算符,因此弹出5和7,计算出7×5=35,将35入栈; (5) 将6入栈; (6) 最后是-运算符,计算出35-6的值,即29,由此得出最终结果。 将中缀表达式转换为后缀表达式: 与转换为前缀表达式相似,遵循以下步骤: (1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2; (2) 从左至右扫描中缀表达式; (3) 遇到操作数时,将其压入S2; (4) 遇到运算符时,比较其与S1栈顶运算符的优先级: (4-1) 如果S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈; (4-2) 否则,若优先级比栈顶运算符的高,也将运算符压入S1(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况); (4-3) 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较; (5) 遇到括号时: (5-1) 如果是左括号“(”,则直接压入S1; (5-2) 如果是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将这一对括号丢弃; (6) 重复步骤(2)至(5),直到表达式的最右边; (7) 将S1中剩余的运算符依次弹出并压入S2; (8) 依次弹出S2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。 例如,将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下:

扫描到的元素

S2(栈底->栈顶)

S1 (栈底->栈顶)

说明

1

1

数字,直接入栈

+

1

+

S1为空,运算符直接入栈

(

1

+ (

左括号,直接入栈

(

1

+ ( (

同上

2

1 2

+ ( (

数字

+

1 2

+ ( ( +

S1栈顶为左括号,运算符直接入栈

3

1 2 3

+ ( ( +

数字

)

1 2 3 +

+ (

右括号,弹出运算符直至遇到左括号

×

1 2 3 +

+ ( ×

S1栈顶为左括号,运算符直接入栈

4

1 2 3 + 4

+ ( ×

数字

)

1 2 3 + 4 ×

+

右括号,弹出运算符直至遇到左括号

-

1 2 3 + 4 × +

-

-与+优先级相同,因此弹出+,再压入-

5

1 2 3 + 4 × + 5

-

数字

到达最右端

1 2 3 + 4 × + 5 -

S1中剩余的运算符

因此结果为“1 2 3 + 4 × + 5 -”(注意需要逆序输出)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏cs

c++那些事儿5.0 模板

模板 是泛型编程的重点,在后面的STL中,模板的功能得到广泛运用。 在java中泛型,集合都有模板的身影,弄清模板可以让我们更加深入学习。 ---- 可讲的...

34212
来自专栏数据之美

基于堆实现的优先级队列:PriorityQueue 解决 Top K 问题

1、认识 PriorityQueue PriorityQueue是从JDK1.5开始提供的新的数据结构接口,它是一种基于优先级堆的极大优先级队列。优先级队...

2315
来自专栏木东居士的专栏

通过源码分析 String、StringBuffer 和 StringBuilder

1463
来自专栏猿天地

java8 stream

转载:猿天地 链接:http://cxytiandi.com/blog/detail/2220 Stream 作为 Java 8 的一大亮点,我个人是非常喜...

3349
来自专栏java 成神之路

JVM基于栈的解释器执行原理

2507
来自专栏郭耀华‘s Blog

剑指offer第三天

21.栈的压入、弹出序列 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,...

2706
来自专栏向治洪

前缀、中缀、后缀表达式

在函数式编程语言中,为了表示方便,出现了一些新的语法格式。所谓前缀、中缀、后缀表达式,它们之间的区别在于运算符相对与操作数的位置不同,为了说明它们的概念,首先来...

1855
来自专栏佳爷的后花媛

设计一个有getMin功能的栈1.设计一个有getMin功能的栈

801
来自专栏Java Web

数据结构与算法(2)——栈和队列栈队列LeetCode 相关题目整理其他题目整理

栈是一种用于存储数据的简单数据结构(与链表类似)。数据入栈的次序是栈的关键。可以把一桶桶装的薯片看作是一个栈的例子,当薯片做好之后,它们会依次被添加到桶里,每一...

813
来自专栏技术与生活

java 对象池技术

1、为什么用对象池 在 java 中,对象的生命周期包括对象创建、对象使用,对象消失三个时间段,其中对象的使用是对象真正需要存活的时间,不好修改,该用的时候...

1114

扫码关注云+社区