http://www.spoj.pl/problems/ONP/
中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式算法
使用一個(gè)數(shù)組作為運(yùn)算符的棧，從頭到尾掃描中綴表達(dá)式，對(duì)不同類型的字符按不同情況處理：
1、如果是數(shù)字則直接放入后綴表達(dá)式數(shù)組；
2、如果是左括號(hào)則直接入棧；
3、如果是右括號(hào)，則把從棧頂直到對(duì)應(yīng)左括號(hào)之間的運(yùn)算符依次退棧，并清除對(duì)應(yīng)的左括號(hào)；
4、對(duì)于運(yùn)算符，如果該運(yùn)算符的優(yōu)先級(jí)大于棧頂優(yōu)先級(jí)，則直接入棧，
若該運(yùn)算符的優(yōu)先級(jí)小于等于棧頂優(yōu)先級(jí)，則先把棧頂運(yùn)算符出棧，寫(xiě)入后綴表達(dá)式數(shù)組，
然后再入棧；
5、掃描完成后，取出棧中所有運(yùn)算符，寫(xiě)入后綴表達(dá)式數(shù)組。
import java.util.*;
import java.io.*;
public class SPOJ_4
{
public static char[] opt = {'(','+','-','*','/','^',')'};
public static boolean compare(char c1,char c2){
int i,j;
for(i=0;i<7;i++){
if(c1==opt[i])
break;
}
for(j=0;j<7;j++){
if(c2==opt[j])
break;
}
if(i>j)
return true;
else
return false;
}
public static void main(String rgs[]) throws Exception
{
BufferedReader stdin =
new BufferedReader(
new InputStreamReader(System.in));
String line = stdin.readLine();
int i,j,n,t = Integer.parseInt(line);
for(i=0;i<t;i++){
line = stdin.readLine();
char[] stack = new char[400];
char c;
int top=0;
n=line.length();
for(j=0;j<n;j++){
c=line.charAt(j);
if(c>='a' && c<='z')
System.out.print(c);
else if(c=='(')
stack[++top]=c;
else if(c==')'){
while(stack[top]!='('){
System.out.print(stack[top]);
top--;
}
top--;
}
else{
if(top==0 || compare(c,stack[top]))
stack[++top]=c;
else{
while(!(top==0 || compare(c,stack[top]))){
System.out.print(stack[top]);
top--;
}
stack[top++]=c;
}
}
}
System.out.println("");
}
}
}posted on 2009-08-22 16:08
飛翔天使 閱讀(246)
評(píng)論(0) 編輯 收藏 所屬分類:
spoj