前缀、中缀、后缀表达式

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

它们都是对表达式的记法,因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与操作数的位置不同:前缀表达式的运算符位于与其相关的操作数之前;中缀和后缀同理。 举例: (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 条评论
登录 后参与评论

相关文章

来自专栏Bingo的深度学习杂货店

Q503 Next Greater Element II

Given a circular array (the next element of the last element is the first elemen...

3226
来自专栏武培轩的专栏

剑指Offer-链表中倒数第k个结点

题目描述 输入一个链表,输出该链表中倒数第k个结点。 思路 为了能够只遍历一次就能找到倒数第k个节点,可以定义两个指针: 快指针从链表的头指针开始遍历向前走k-...

3249
来自专栏desperate633

LintCode 平面列表题目分析代码

给定一个列表,该列表中的每个要素要么是个列表,要么是整数。将其变成一个只包含整数的简单列表。 ** 注意事项 ** 如果给定的列表中的要素本身也是一个列表,...

552
来自专栏郭耀华‘s Blog

《剑指offer》全部题目-含Java实现

陆续刷了好久,算是刷完了《剑指offer》,以下全部AC代码,不一定性能最优,如有错误或更好解答,请留言区指出,大家共同交流,谢谢~ 1.二维数组中的查找 在...

6077
来自专栏desperate633

LeetCode 349. Intersection of Two Arrays题目代码代码

样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].

421
来自专栏云霄雨霁

离散数学中集合上二元关系的判定及实现

3130
来自专栏mathor

数制

855
来自专栏Bingo的深度学习杂货店

Q20 Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', d...

2644
来自专栏云霄雨霁

字符串查找----三向单词查找树

1351
来自专栏Golang语言社区

厚土Go学习笔记 | 26. 函数闭包

如果非必要,尽量不要在程序中使用闭包。 go函数可以是一个闭包。闭包是一个函数值,它引用了函数体之外的变量。这个函数可以对这个变量进行访问和赋值。 展示一个例子...

34813

扫码关注云+社区