字首，中綴，字尾表達式轉換

title: 字首，中綴，字尾表達式轉換

date: 2017-09-10 19:45:09

categories: ‘technology’

tags:

- ‘算法’

1 基本概念

​ 在計算機中表達式有三種，字首表達式（波蘭式），中綴表達式，字尾表達式（逆波蘭式）。

如表達式：a+b*(c-d)-e/f

字首表達式：-+a*b-cd/ef

中綴表達式：a+b*(c-d)-e/f

字尾表達式：abcd-*+ef/-

2 轉換原理

​ 原理不難，我們遇到遇到操作數的時候直接輸出，當遇到操作符（包括‘（’，‘+’，‘-’，‘*’，‘/’）的時候，我們需要把符号壓入到棧中，

• 2.1 當遇到‘）’的時候：

​ 我們需要依次從棧頂彈出符号，直到遇到‘（’，并且要将‘（’彈出。如：（a*（b+c）），棧中的是（*（+，當遇到‘）’的時候，我們要彈出‘+’，‘（’。

• 2.2 當遇到‘（’的時候

​ 此時沒什麼要說的，直接壓棧。

• 2.3 當遇到‘+’，‘-’，‘*’，‘/’的時候：

​ 我們要把棧頂元素的符号的優先級跟輸入的符号的優先級進行對比，如果棧頂優先級高的話，我們就要把棧頂元素依次彈出，直到棧頂的優先級低于輸入的優先級或者棧空。

如：a+b+c+d，跟a+b*c+d得到的符号順序就不一樣，原因就是這個優先級的問題。

• 2.4 當遇到操作數的時候：

​ 毫無疑問，直接輸出

例題：

簡便方法

中綴表達式(a+b) * c * (d-e/f) 轉成字首，字尾表達式

• 第一步：按照運算符的優先級對所有的運算機關加括号：式子變成了：((a+(b*c))-(d+e)) 
• 第二步：轉換字首與字尾表達式 
• 字首：把運算符号移動到對應的括号前面,則變成拉：-( +(a *(bc)) +(de)) 。把括号去掉：-+a*bc+de 字首式子出現 
• 字尾：把運算符号移動到對應的括号後面，則變成拉：((a(bc)* )+ (de)+ )- 。把括号去掉：abc*+de+- 字尾式子出現