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
飞翔天使 阅读(242)
评论(0) 编辑 收藏 所属分类:
spoj