http://www.spoj.pl/problems/ONP/
中綴表達式轉換為后綴表達式算法
使用一個數組作為運算符的棧，從頭到尾掃描中綴表達式，對不同類型的字符按不同情況處理：
1、如果是數字則直接放入后綴表達式數組；
2、如果是左括號則直接入棧；
3、如果是右括號，則把從棧頂直到對應左括號之間的運算符依次退棧，并清除對應的左括號；
4、對于運算符，如果該運算符的優先級大于棧頂優先級，則直接入棧，
若該運算符的優先級小于等于棧頂優先級，則先把棧頂運算符出棧，寫入后綴表達式數組，
然后再入棧；
5、掃描完成后，取出棧中所有運算符，寫入后綴表達式數組。
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)
評論(0) 編輯 收藏 所屬分類:
spoj