日期:2014-05-20  浏览次数:20689 次

求指导:用堆栈求一个字符串表达式的值
    网上弄了一段代码,主要思想是:先把字符串切成一个个的字符压入栈中(按照一定规则:逆波兰式),到此即可把中缀表示法转换成后缀表示法(逆波兰式),再经过一次堆栈运算即可得到答案。
    但问题是这种情况下表达式中不能有大于10的数字,比如9*(1+6),如果是10*(1+6)即出错。求高人指点。

------解决方案--------------------
不仅仅能匹配整数,还能匹配浮点数,不知道是否符合你的意图?



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){