逆波蘭表達式:逆波蘭表達式又叫做後綴表達式。在通常的表達式中，二元運算符 -百科知識中文網

逆波蘭表達式

逆波蘭表達式，它的語法規定，表達式必須以逆波蘭表達式的方式給出。逆波蘭表達式又叫做後綴表達式。這個知識點在數據結構和編譯原理這兩門課程中都有介紹，下面是一些例子：
正常的表達式逆波蘭表達式
a+b ---> a,b,+
a+(b-c) ---> a,b,c,-,+
a+(b-c)*d ---> a,b,c,-,d,*,+
a+d*(b-c)--->a,d,b,c,-,*,+
a=1+3 ---> a=1,3 +
http=(smtp+http+telnet)/1024 寫成什麼呢？
http=smtp,http,telnet,+,+,1024,/

逆波蘭表達式的用途

逆波蘭表達式是一種十分有用的表達式，它將複雜表達式轉換為可以依靠簡單的操作得到計算結果的表達式。例如(a+b)*(c+d)轉換為ab+cd+*

逆波蘭表達式的優勢

它的優勢在於只用兩種簡單操作，入棧和出棧就可以搞定任何普通表達式的運算。其運算方式如下：
如果當前字元為變數或者為數字，則壓棧，如果是運算符，則將棧頂兩個元素彈出作相應運算，結果再入棧，最後當表達式掃描完後，棧里的就是結果。

一般算法

將一個普通的中序表達式轉換為逆波蘭表達式的一般算法是：
(1)首先構造一個運算符棧，此運算符在棧內遵循越往棧頂優先權越高的原則。
(2)讀入一個用中綴表示的簡單算術表達式，為方便起見,設該簡單算術表達式的右端多加上了優先權最低的特殊符號“#”。
(3)從左至右掃描該算術表達式，從第一個字元開始判斷，如果該字元是數字，則分析到該數字串的結束並將該數字串直接輸出。
(4)如果不是數字，該字元則是運算符，此時需比較優先關係。
做法如下：將該字元與運算符棧頂的運算符的優先關係相比較。如果，該字元優先關係高於此運算符棧頂的運算符，則將該運算符入棧。倘若不是的話，則將棧頂的運算符從棧中彈出，直到棧頂運算符的優先權低於當前運算符，將該字元入棧。
(5)重複上述操作(3)-(4)直至掃描完整個簡單算術表達式，確定所有字元都得到正確處理，我們便可以將中綴式表示的簡單算術表達式轉化為逆波蘭表示的簡單算術表達式。

算法流程

下面是程式化算法流程：
1、建立運算符棧stackOperator用於運算符的存儲，壓入'\0'。
2、預處理表達式，正、負號前加0(如果一個加號（減號）出現在最前面或左括弧後面，則該加號（減號）為正負號) 。
3、順序掃描表達式，如果當前字元是數字（優先權為0的符號），則直接輸出該數字；如果當前字元為運算符或括弧（優先權不為0的符號），則判斷第4點。
4、若當前運算符為'('，直接入棧；
若為')'，出棧並順序輸出運算符直到遇到第一個'('，遇到的第一個'('出棧但不輸出；
若為四則運算符，比較棧頂元素與當前元素的優先權：
如果棧頂元素運算符優先權 >= 當前元素的優先權，出棧並順序輸出運算符直到棧頂元素優先權 < 當前元素優先權，然後當前元素入棧；
如果棧頂元素 < 當前元素，直接入棧。
5、重複第3點直到表達式掃描完畢。
6、順序出棧並輸出運算符直到棧頂元素為'\0'。
int Precedence(char sign)
{
switch(sign)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
case '%':
return 3;
case '(':
case '@':
default:
return 0;
}
}
/****************中綴表達式轉換成後綴表達式 ********************/
void Change(char* s1,char* s2)
{
seqstack T;
int i=0,j=0;
char ch;
SetNull(&T);
Push(&T,'@');
ch=s1[i];
while(ch!="\0")
{
if(ch==" ")
ch=s1[++i];
else if(ch=="(")
{
Push(&T,ch);
ch=s1[++i];
}
else if(ch==")")
{
while(GetTop(&T)!="(")
s2[j++]=Pop(&T);
Pop(&T);
ch=s1[++i];
}
else if(ch=="" || ch=="-" ||ch=="*" ||ch=="/" ||ch=="^" ||ch=="%")
{
char w=GetTop(&T);
while(Precedence(w)>=Precedence(ch))
{
s2[j++]=w;
Pop(&T);
w=GetTop(&T);
}
Push(&T,ch);
ch=s1[++i];
}
else
{
while((ch>="0" && ch<="9")||ch==".")
{
s2[j++]=ch;
ch=s1[++i];
}
s2[j++]=" ";
}
}
ch=Pop(&T);
while(ch!="@")
{
s2[j++]=ch;
ch=Pop(&T);
}
s2[j++]="\0";
}

優先權分類

優先權分為棧內優先權isp(In stack priority)和棧外優先權icp(In coming priority)。除了括弧以外，其他運算符進棧後優先權都升1，這樣可以體現在中綴表達式中相同優先權的操作符自左向右計算的要求，讓位於棧頂的操作符先退棧並輸出。
各運算符及符號優先權：

操作符	#	^	*,/,%	+,-	(	)
isp	0	7	5	3	1	8
icp	0	6	4	2	8	1

逆波蘭表達式