人們平常使用的運算式，是將運算元放在運算子兩旁，例如a + b / d 這樣的式子，這稱為中序（infix）表示式；然而電腦剖析運算式時，為了有效率地.
OPENHOME.CC
常見程式演算
|老掉牙
河內塔
費式數列
巴斯卡三角形
三色旗
老鼠走迷宮
騎士走棋盤
八皇后
八銀幣
康威生命遊戲
字串比對
背包問題
雙色、三色河內塔
得分排行
|「數」
最大訪客數
Eratosthenes篩選求質數
完美數
阿姆斯壯數
大數運算
指定位數的圓周率
|隨機
蒙地卡羅法求PI
洗牌
Craps賭博遊戲
約瑟夫問題
|組構
排列
格雷碼
子集
k組合
因數分解
加法因子
|排序
選擇、插入、氣泡排序
Heap排序-改良的選擇排序
Shell排序-改良的插入排序
Shaker排序-改良的氣泡排序
快速排序（一）
快速排序（二）
合併排序
基數排序
|搜尋
線性搜尋
二分搜尋
插補搜尋
費氏搜尋
|矩陣
稀疏矩陣
多維矩陣降維
上／下三角、對稱矩陣
奇數魔方陣
4N魔方陣
2(2N+1)魔方陣
|運算
中序式轉後序式
後序式運算
Quine
GitHub
Twitter
Facebook
LinkedIn
Designs
Tags
BuiltwithbyHugo
HOME>
常見程式演算>
運算>
中序式轉後序式
解法思路
程式實作
postfix
infix
parser
computation
C
Java
Python
Scala
Ruby
JavaScript
Haskell
中序式轉後序式
December12,2021
人們平常使用的運算式，是將運算元放在運算子兩旁，例如a+b/d這樣的式子，這稱為中序（infix）表示式；然而電腦剖析運算式時，為了有效率地判斷運算的順序，可將中序表示式轉換為後序（postfix）或前序（prefix）表示式。
解法思路
後序表示式又稱為逆向波蘭表示式（reversepolishnotation），是由波蘭的數學家盧卡謝維奇提出，例如(a+b)*(c+d)，表示為後序表示式時是ab+cd+*。
想以人工轉換計算後序式的話，可以使用括號法，將運算子兩旁的運算元，依先後順序全部括號起來，然後將右括號取代為左邊最接近的運算子（從最內層括號開始），最後去掉全部的左括號就可以完成。
例如：
a+b*d+c/d
((a+(b*d))+(c/d))
abd*+cd/+
另一個方式是堆疊法，使用迴圈取出中序式的元素，遇運算元直接輸出，遇到運算子與左括號進行堆疊，堆疊中運算子優先順序若大於等於讀入的運算子優先順序，直接輸出堆疊中的運算子，再將讀入的運算子置入堆疊；遇右括號輸出堆疊中的運算子至左括號。
以下是虛擬碼的運算法，\0表示中序式讀取完畢：
ProcedurePostfix(infix)[
Loop[
op=infix(i)
case[
:x='\0':
while(stacknotempty)
//outputallelementsinstack
end
return
:x='(':
//putitintostack
:xisoperator:
while(priority(stack[top])>=
priority(op))[
//outaelementfromstack
]
//saveopintostack
:x=')':
while(stack(top)!='(')[
//outaelementfromstack
]
top=top-1//notout'(
:else:
//outputcurrentop
]
i++;
]
]
例如(a+b)*(c+d)，依演算法的輸出過程如下：
元素
堆疊
輸出
(
(
-
a
(
a
+
(+
a
b
(+
ab
)
-
ab+
*
*
ab+
(
*(
ab+
c
*(
ab+c
+
*(+
ab+c
d
*(+
ab+cd
)
*
ab+cd+
-
-
ab+cd+*
若要用堆疊法將中序式轉為前序式，使用迴圈由後往前取出中序式的字元，遇運算元直接輸出；遇運算子與右括號進行堆疊；堆疊中運算子優先順序若大於讀入的運算子優先順序，直接輸出堆疊中的運算子，再將讀入的運算子置入堆疊；遇左括號輸出堆疊中的運算子至右括號。
程式實作
C
Java
Python
Scala
Ruby
JavaScript
Haskell
#include
#include
#defineMAX80
voidinToPostfix(char*,char*);//中序轉後序
intpriority(char);//運算子優先權
intmain(void){
charinfix[MAX]={'\0'};
charpostfix[MAX]={'\0'};
printf("中序運算式：");
scanf("%s",infix);
inToPostfix(infix,postfix);
inti;
for(i=0;postfix[i]!='\0';i++){
printf("%c",postfix[i]);
}
return0;
}
voidinToPostfix(char*infix,char*postfix){
charstack[MAX]={'\0'};
inti,j,top;
for(i=0,j=0,top=0;infix[i]!='\0';i++)switch(infix[i]){
case'('://運算子堆疊
stack[++top]=infix[i];
break;
case'+':case'-':case'*':case'/':
while(priority(stack[top])>=priority(infix[i])){
postfix[j++]=stack[top--];
}
stack[++top]=infix[i];//存入堆疊
break;
case')':
while(stack[top]!='('){//遇)輸出至(
postfix[j++]=stack[top--];
}
top--;//不輸出(
break;
default://運算元直接輸出
postfix[j++]=infix[i];
}
while(top>0){
postfix[j++]=stack[top--];
}
}
intpriority(charop){
switch(op){
case'+':case'-':return1;
case'*':case'/':return2;
default:return0;
}
}
importjava.util.*;
importstaticjava.lang.System.out;
publicclassInfix{
privatestaticintpriority(charc){
returnc=='+'||c=='-'?1:c=='*'||c=='/'?2:0;
}
privatestaticStringtoPostfix(Stringinfix,booleanisPost){
Stringexpr=isPost?
infix:newStringBuffer(infix).reverse().toString();
LinkedListstack=newLinkedList<>();
StringBuilderoutput=newStringBuilder();
chartoStack=isPost?'(':')';
chartoOutput=isPost?')':'(';
for(charc:expr.toCharArray()){
if(c==toStack){stack.add(c);}
elseif("+-*/".indexOf(c)!=-1){
while(!stack.isEmpty()&&
priority(stack.getLast())>=priority(c)){
output.append(stack.removeLast());
}
stack.add(c);
}
elseif(c==toOutput){
while(stack.getLast()!=toStack){
output.append(stack.removeLast());
}
stack.removeLast();
}
else{output.append(c);}
}
while(!stack.isEmpty()){output.append(stack.removeLast());}
returnisPost?output.toString():output.reverse().toString();
}
publicstaticStringtoPostfix(Stringinfix){
returntoPostfix(infix,true);
}
publicstaticStringtoPrefix(Stringinfix){
returntoPostfix(infix,false);
}
publicstaticvoidmain(String[]args){
Stringinfix="(a+b)*(c+d)";
out.println(toPostfix(infix));
out.println(toPrefix(infix));
}
}
defpriority(op):
return1ifopin"+-"else2ifopin"*/"else0
deftoPostfix(infix,isPost=True):
toStack,toOutput=('(',')')ifisPostelse(')','(')
defprocOpt(c,stack,output):
ifstack==""orpriority(stack[-1])1
case'*'|'/'=>2
case_=>0
}
deftoPostfix(infix:String,isPost:Boolean=true)={
val(toStack,toOutput)=if(isPost)('(',')')else(')','(')
defprocOpt(c:Char,stack:String,output:String):(String,String)={
if(stack==""||priority(stack.last)(c,stack,output){
ifstack==""||priority(stack[-1])(stack,output){
ifstack[-1]==toStack
[stack[0...-1],output]
else
procPhs.call(stack[0...-1],output+stack[-1])
end
}
procExpr=->(expr,stack="",output=""){
ifexpr==""
output+stack.reverse
elsifexpr[0]==toStack
procExpr.call(expr[1..-1],stack+expr[0],output)
elsif"+-*/".include?expr[0]
procExpr.call(expr[1..-1],*procOpt.call(expr[0],stack,output))
elsifexpr[0]==toOutput
procExpr.call(expr[1..-1],*procPhs.call(stack,output))
else
procExpr.call(expr[1..-1],stack,output+expr[0])
end
}
output=procExpr.call(isPost?infix:infix.reverse)
isPost?output:output.reverse
end
deftoPrefix(infix)
toPostfix(infix,false)
end
infix="(a+b)*(c+d)"
puts(toPostfix(infix))
puts(toPrefix(infix))
Array.prototype.getLast=function(){
returnthis[this.length-1];
};
Array.prototype.isEmpty=function(){
returnthis.length==0;
};
functionpriority(c){
returnc==='+'||c==='-'?1:c==='*'||c==='/'?2:0;
}
functiontoPostfix(infix,isPost){
isPost=isPost===undefined?true:false;
varexpr=isPost?infix.split(''):infix.split('').reverse();
varstack=[];
varoutput=[];
vartoStack=isPost?'(':')';
vartoOutput=isPost?')':'(';
expr.forEach(function(c){
if(c===toStack){stack.push(c);}
elseif('+-*/'.indexOf(c)!==-1){
while(!stack.isEmpty()&&
priority(stack.getLast())>=priority(c)){
output.push(stack.pop());
}
stack.push(c);
}
elseif(c===toOutput){
while(stack.getLast()!==toStack){
output.push(stack.pop());
}
stack.pop();
}
else{output.push(c);}
});
while(!stack.isEmpty()){output.push(stack.pop());}
returnisPost?output.join(''):output.reverse().join('');
}
functiontoPrefix(infix){
returntoPostfix(infix,false);
}
varinfix="(a+b)*(c+d)";
print(toPostfix(infix));
print(toPrefix(infix));
priorityop=ifop`elem`"+-"then1
elseifop`elem`"*/"then2
else0
toPfixinfisPost=ifisPostthenoutputelsereverseoutput
where
(toStack,toOutput)=ifisPostthen('(',')')else(')','(')
output=procExpr(ifisPosttheninfelsereverseinf)("","")
procOptcstackoutput=
ifstack==""||(priority$laststack)
