五分钟小知识之什么是后缀表达式
source link: https://www.cxyxiaowu.com/919.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
点击蓝色“五分钟学算法”关注我哟
加个“星标”，一起学算法
后缀表达式，又称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。
后缀表达式计算：
后缀表达式计算与前缀表达式类似，只是顺序是从左至右，具体过程如下：
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
例如：后缀表达式为“2 3 + 4 × 5 -”计算过程如下：
（1）从左至右扫描，将 2 和 3 压入堆栈；
（2）遇到 + 运算符，因此弹出 3 和 2（ 3 为栈顶元素，2 为次顶元素，注意与前缀表达式做比较），计算出 3+2 的值，得 5，再将 5 入栈；
（3）将 4 入栈；
（4）接下来是 × 运算符，因此弹出 4 和 5，计算出 4 × 5 = 20，将 20 入栈；
（5）将 5 入栈；
（6）最后是-运算符，计算出 20-5 的值，即 15，由此得出最终结果。
中缀表达式转后缀表达式：
与转换为前缀表达式相似，步骤如下：
（1）初始化两个栈：运算符栈s1和储存中间结果的栈s2；
（2）从左至右扫描中缀表达式；
（3）遇到操作数时，将其压s2；
（4）遇到运算符时，比较其与 s1 栈顶运算符的优先级：
a：如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
b：否则，若优先级比栈顶运算符的高，也将运算符压入 s1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）;
c：否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到（4）-（1）与s1中新的栈顶运算符相比较；
（5）遇到括号时：
a：如果是左括号“(”，则直接压入 s1；
b：如果是右括号“)”，则依次弹出 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 – ”
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK