四则运算的简单模拟(栈的运用)

说明：程序只是为了说明计算规则(思路)，并未优化，可能还是存在一些BUG(未进行大量数据的反复验证),必有更好的实现方式！！！
另外，在计算过程中，由于采用int，因此对于如5/3*3并不是5，而是3，所以可能计算结果有点出入！！！


栈：先进后出
四则运算的运用：
①将中缀表达式转为后缀表达式
规则1：若出现的符号等级低于栈顶的表达式等级(如符号为'+或-'，而栈顶为'*或/'，则除顶部自己外其余全部出栈；若碰到同级则只出栈一个(如符号为'+'，而栈顶为'-'且栈中还有'+-'，则只出栈顶一个'-')
规则2：若出现左右括号，则括号内的内容全部出栈
规则3：非符号(即数字)不用进栈，只需依次记录即可
②入栈计算后缀表达式并得出结果
规则：类似"56*"则计算为5*6=30，然后30入栈继续计算

附上代码如下：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Test {

	public static void main(String[] args) {
		//Test1
		String str1[] = {"9","+","(","3","-","1",")","*","3","+","10","/","2"};
		System.out.println(calculateInfixExpression(infixExpression2PostfixExpression(str1)));
		//Test2
		String str2[] = {"3","+","6"};
		System.out.println(calculateInfixExpression(infixExpression2PostfixExpression(str2)));
		//Test3
		String str3[] = {"13","-","6","/","2","-","1","+","3","*","5","/","3"};
		System.out.println(calculateInfixExpression(infixExpression2PostfixExpression(str3)));
		//Test4
		String str4[] = {"4","/","2","+","1","-","5","+","3","*","6","/","2"};
		System.out.println(calculateInfixExpression(infixExpression2PostfixExpression(str4)));
	}
	
	//将中缀表达式转为后缀表达式
	public static List<String> infixExpression2PostfixExpression(String str[]){
		List<String> sb = new ArrayList<String>();
		Stack<String> s = new Stack<String>();
		for(int i=0;i<str.length;i++){
			if(str[i].equals("+")||
			   str[i].equals("-")||		
			   str[i].equals("*")||		
			   str[i].equals("/")||		
			   str[i].equals("(")||
			   str[i].equals(")")
			){
				if(s.contains("(")&&str[i].equals(")")){
					s.push(str[i]);
					Stack<String> ss = new Stack<String>();
					ss.addAll(s);
					int count = ss.size();
					int removeCount = 0;
					for(int m=0;m<count;m++){
						String pop = ss.pop();
						if((!(pop.equals("(")))&&
						   (!(pop.equals(")")))){
							sb.add(pop);
							removeCount++;
						}else if(pop.equals("(")){
							break;
						}
					}
					//+2表示算上左右括号
					for(int n=1;n<=(removeCount+2);n++){
						s.pop();
					}
				}else if((str[i].equals("+")&&((s.isEmpty()?"":s.lastElement()).equals("*")||(s.isEmpty()?"":s.lastElement()).equals("/")))||
						 (str[i].equals("-")&&((s.isEmpty()?"":s.lastElement()).equals("*")||(s.isEmpty()?"":s.lastElement()).equals("/")))||
						 (str[i].equals("*")&&((s.isEmpty()?"":s.lastElement()).equals("/")))||
						 (str[i].equals("/")&&((s.isEmpty()?"":s.lastElement()).equals("*")))||
						 (str[i].equals("+")&&((s.isEmpty()?"":s.lastElement()).equals("-")))||                                                                    
						 (str[i].equals("-")&&((s.isEmpty()?"":s.lastElement()).equals("+")))){
					if((str[i].equals("+")&&(s.lastElement().equals("*")||s.lastElement().equals("/")))||
					   (str[i].equals("-")&&(s.lastElement().equals("*")||s.lastElement().equals("/")))	){
						s.push(str[i]);
						String sss = "";
						int length = s.size();
						for(int k=0;k<length;k++){
							if(k==0){
								sss = s.pop();
							}else{
								sb.add(s.pop());
							}
						}
						s.push(sss);
					}else{
						sb.add(s.pop());
						s.push(str[i]);
					}
				}else{
					s.push(str[i]);
				}
			}else{
				sb.add(str[i]);
			}
		}
		//最后还有剩余则出栈
		int restLength = s.size();
		for(int o=0;o<restLength;o++){
			sb.add(s.pop());
		}
		return sb;
	}

	//将后缀表达式入栈计算并得出最终结果
	public static String calculateInfixExpression(List<String> list){
		System.out.println(list);
		Stack<String> s = new Stack<String>();
		for(int i=0;i<list.size();i++){
			String data = list.get(i);
			if(data.equals("+")||data.equals("-")||data.equals("*")||data.equals("/")){
				int firstPop = Integer.parseInt(s.pop());
				int secondtPop = Integer.parseInt(s.pop());
				int result = 0;
				switch(data){
					case "+":
						result = secondtPop+firstPop;
						break;
					case "-":
						result = secondtPop-firstPop;
						break;
					case "*":
						result = secondtPop*firstPop;
						break;
					case "/":
						result = secondtPop/firstPop;
						break;
				}
				s.push(String.valueOf(result));
			}else{
				s.push(data);
			}
		}
		//最后应该总是还剩一个
		return s.pop();
	}

}

评论

1 楼 comsci 2014-07-21  

高手啊....经典