日期:2014-05-20 浏览次数:20689 次
import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import org.junit.Test;
/**
*计算表达式
1、用正则匹配出用户输入的表达式,得到含有括号、数字、运算符的中缀集合
2、中缀--->后缀
3、计算后缀
*
*/
public class Biaodashi {
/**
*中缀表达式转后缀表达式 http://baike.baidu.com/view/339689.htm
*
*遍历中缀的list
*1、数字时,加入后缀list
*2、“(”时,压栈
*3、 若为 ')',则依次弹栈,把弹出的运算符加入后缀表达式中,直到出现'(';
*4、若为运算符,对做如下处置
* 1、如果栈为空,则压栈
* 2、如果栈不为空:
* 1、stack.peek().equals("(") 则压栈
* 2、比较str和stack.peek()的优先级
* 1、如果>,则运算符压栈
* 2、<=的情况:当栈不为空时:
* 1、stack.peek()是左括号,压栈
* 2、<=,把peek加入后缀表达式,弹栈
* 3、>,把运算符压栈,停止对栈的操作
* 执行完栈的操作之后,还得判断:如果栈为空,运算符压栈
*/
public List<String> midToAfter(List<String> midList){
List<String> afterList=new ArrayList<String>();
Stack<String> stack=new Stack<String>();
for(String str:midList){
int flag=this.matchWitch(str);
switch (flag) {
case 7:
afterList.add(str);
break;
case 1:
stack.push(str);
break;
case 2:
String pop=stack.pop();
while(!pop.equals("(")){
afterList.add(pop);
pop=stack.pop();
}
break;
default:
if(stack.isEmpty()){
stack.push(str);
break;
}
else{
if(stack.peek().equals("(")){
stack.push(str);
break;
}else{
int ji1=this.youxianji(str);
int ji2=this.youxianji(stack.peek());
if(ji1>ji2){
stack.push(str);
}else{
while(!stack.isEmpty()){
String f=stack.peek();
if(f.equals("(")){
stack.push(str);
break;
}else{
if(this.youxianji(str)<=this.youxianji(f)){
afterList.add(f);
stack.pop();
}else{
stack.push(str);
break;
}
}
}
if(stack.isEmpty()){
stack.push(str);
}
}
break;
}
}
}
}
while(!stack.isEmpty()){
afterList.add(stack.pop());
}
StringBuffer sb=new StringBuffer();
for(String s:afterList){
sb.append(s+" ");
}
//System.out.println(sb.toString());
return afterList;
}
/**
判断运算符的优先级
*/
public int youxianji(String str){