算术运算的设计

package come.feiqiang.stack;

import java.util.Scanner;
import java.util.Stack;
import java.util.regex.Pattern;

public class Algorithm {
	
	/**
	 * 验证各种括号的匹配问题，是对栈的基本应用：
	 * @param expression
	 * @return
	 */
	public static boolean isBalanced(String expression){
		final char LEFT_NOMAL='(';
		final char RIGHT_NOMAL=')';
		final char LEFT_CURLY='{';
		final char RIGHT_CURLY='}';
		final char LEFT_SQUARE='[';
		final char RIGHT_SQUARE=']';
		
		Stack<Character> store=new Stack<Character>();
		int i;
		boolean failed=false;
		for(i=0;!failed&&i<expression.length();i++){
			switch(expression.charAt(i)){
				case LEFT_NOMAL:
				case LEFT_CURLY:
				case LEFT_SQUARE:
					store.push(expression.charAt(i));
					break;
				case RIGHT_NOMAL:
					if(store.isEmpty()||store.pop()!=LEFT_NOMAL){
						failed=true;
					}
					break;
				case RIGHT_CURLY:
					if(store.isEmpty()||store.pop()!=LEFT_CURLY){
						failed=true;
					}
					break;
				case RIGHT_SQUARE:
					if(store.isEmpty()||store.pop()!=LEFT_SQUARE){
						failed=true;
					}
					break;
			}
		}
		return (store.isEmpty()&&!failed);
	}
	
	/**
	 * 计算完全加括号的算术：
	 * @param numbers 数字栈
	 * @param operations 操作符栈
	 * 算法：
	 * do
	 * 		if(下一个输入是数值)
	 * 			进数值栈
	 	 	else if(下一个输入是操作符)
	 * 			进操作符栈
	 * 		else if(下一个输入是右括号)
	 * 			弹出两个数值，弹出一个操作符，将后弹出的数值与前弹出的数值作运算，将操作结果压入数值栈
	 * 			如果栈为空，或操作数为空，抛出异常
	 * 		else if(下一个输入是左括号)
	 * 			跳过
	 * 		else 抛出非法字符异常
	 *while(还有更多输入) 
	 * 算法缺点：没有检查括号的正确匹配情况，有兴趣的读者可以自己研究一下
	 * 
	 */
	public static void evaluateStackTops(Stack<Double> numbers, Stack<Character> operations){
		double operand1;
		double operand2;
		operand1=numbers.pop();
		operand2=numbers.pop();
		char operation=operations.pop();
		
		switch(operation){
			case '+':
				numbers.push(operand1+operand2);
				break;
			case '-':
				numbers.push(operand1-operand2);
				break;
			case '*':
				numbers.push(operand1*operand2);
				break;
			case '/':
				numbers.push(operand1/operand2);
				break;
			default:
				throw new IllegalArgumentException("Illegal Operation");
		}
	}
	public static double evaluate(String expression){
		Stack<Double> numbers=new Stack<Double>();
		Stack<Character> operations=new Stack<Character>();
		
		Scanner input=new Scanner(expression);
		String next;
		
		final Pattern CHARACTER=Pattern.compile("\\S.*?");
		final Pattern UNSIGN_DOUBLE=Pattern.compile("(((\\d+\\.?\\d*)|(\\.\\d+))([Ee][+-]?\\d+)?.*?)");
		
		while(input.hasNext()){
			if(input.hasNext(UNSIGN_DOUBLE)){
				next=input.findInLine(UNSIGN_DOUBLE);
				numbers.push(new Double(next));
			}
			else{
				next=input.findInLine(CHARACTER);
				switch(next.charAt(0)){
					case '+':
					case '-':
					case '*':
					case '/':
						operations.push(next.charAt(0));
						break;
					case ')':
						evaluateStackTops(numbers,operations);
						break;
					case '(':
						break;
					default:
						throw new IllegalArgumentException("Illegal character");
				}
			}
		}
		if(numbers.size()!=1){
			throw new IllegalArgumentException("Illegal input Exception");
		}
		return numbers.pop();
	}
	/**
	 * 后缀表达式的计算：
	 * @param expression
	 * @return
	 * 算法：
	 * 初始化一个由双精度实数构成的栈
	 * while(表达式中有更多输入)
	 * 		if(下一个输入是数值)
	 * 			读取下一个元素并压入栈中
	 * 		else
	 * 			(下一个输入是操作符)
	 * 			弹出两个操作数，根据操作符运算后将结果压入栈中
	 * while end
	 * 
	 */
	public static double evaluatePostfix(String expression){
		double answer;
		Scanner scanner=new Scanner(expression);
		Stack<Double> numbers=new Stack<Double>();
		
		Pattern UNSIGN_DOUBLE=Pattern.compile("((\\d+\\.?\\d*)|(\\.\\d+))([Ee][+-]?\\d+)?.*?");
		Pattern CHARACTER=Pattern.compile("\\S.*?");
		
		while(scanner.hasNext()){
			if(scanner.hasNext(UNSIGN_DOUBLE)){
				numbers.push(new Double(scanner.findInLine(UNSIGN_DOUBLE)));
			}
			else if(scanner.hasNext(CHARACTER)){
				double operand2=numbers.pop();
				double operand1=numbers.pop();
				switch(scanner.findInLine(CHARACTER).charAt(0)){
					case '+':numbers.push(operand1+operand2);break;
					case '-':numbers.push(operand1-operand2);break;
					case '*':numbers.push(operand1*operand2);break;
					case '/':numbers.push(operand1/operand2);break;
					default:throw new IllegalArgumentException("the expression is't right");
				}
			}
			else{
				throw new IllegalArgumentException("the expression is't right");
			}
		}
		if(numbers.size()!=1){
			throw new IllegalArgumentException("illegal expression");
		}
		answer=numbers.pop();
		return answer;
	}
	/**
	 * 由普通的中缀表达是转化为后缀表达式：
	 * @param expression
	 * @return
	 * 算法：
	 * 	略
	 */
	public static String convertMidToPost(String expression){
		String answer="";
		
		Stack<Character> operations=new Stack<Character>();
		Pattern UNSIGN_DOUBLE=Pattern.compile("((\\d+\\.?\\d*)|(\\.\\d+))([Ee][+-]?\\d+)?.*?");
		Pattern CHARACTER=Pattern.compile("\\S.*?");
		Scanner scanner=new Scanner(expression);
		
		while(scanner.hasNext()){
			if(scanner.hasNext(UNSIGN_DOUBLE)){
				answer+=scanner.findInLine(UNSIGN_DOUBLE)+" ";
			}
			else{
				char m;
				if(scanner.hasNext(CHARACTER)){
						switch((m=scanner.findInLine(CHARACTER).charAt(0))){
							case '+':
							case '-':
							case '*':
							case '/':
							case '(':
								operations.push(m);break;
							case ')':
								char c=operations.pop();
								if((operations.isEmpty())||(c!='+'&&c!='-'&&c!='*'&&c!='/')){
									throw new IllegalArgumentException("not valid expression");
								}
								answer+=String.valueOf(c)+" ";
								if(operations.pop()!='('){
									throw new IllegalArgumentException("not valid expression");
								}
								break;
							default:
								throw new IllegalArgumentException("not valid expression");
						}
				}
			}
		}
		return answer;
	}
	/**
	 * 带有优先级的中缀表达式的求解
	 * @param expression
	 * @return
	 * 算法：
	 * 初始化一个空字符串和一个字符栈
	 * while(表达式还有更多输入)
	 * 		if(下一个输入为数值)
	 * 			读取下一个输入，并入字符串尾部
	 * 		else
	 * 			 if(下一个输入是优先级较高的（*,/）运算符||当前栈为空||当前栈顶元素为'(')
	 * 					读取字符下一个输入符号
	 * 			 else if(下一个输入是'(')
	 * 					读取字符并且压入栈中
	 * 			 else if(下一个输入是')')
	 * 					将当前栈中元素全部加入字符串尾部
	 * 			 else if(下一个输入是运算符)
	 * 					将栈中的符号弹出，并入字符串尾部
	 * 					读取下一个字符串，并且压入栈中
	 * 			 else
	 * 					弹出非法表达是一茶馆
	 * while end
	 * 
	 * 下面的代码与算法稍有差别，因为算法是后写的，所以算法的入错能力更强
	 */
	public static String priorityOfMid(String expression){
		String answer="";
		
		Scanner scanner=new Scanner(expression);
		Pattern UNSIGN_DOUBLE=Pattern.compile("((\\d+\\.?\\d*)|(\\.\\d+))([Ee][+-]?\\d+)?.*?");
		Pattern CHARACTER=Pattern.compile("\\S.*?");
		Stack<Character> operations=new Stack<Character>();
		
		if(!scanner.hasNext()){
			throw new IllegalArgumentException("illegal exception");
		}
		
		while(scanner.hasNext()){
			if(scanner.hasNext(UNSIGN_DOUBLE)){
				answer+=scanner.findInLine(UNSIGN_DOUBLE)+" ";
			}else{
				char occurrence=scanner.findInLine(CHARACTER).charAt(0);
				if((operations.isEmpty()||operations.peek()=='(')||(occurrence=='*'||occurrence=='/')&&(operations.peek()=='+'||operations.peek()=='-')){
					System.out.println("in 1");
					operations.push(occurrence);
				}else if(occurrence=='('){
					operations.push(occurrence);
					System.out.println("in 2");
				}else if(occurrence==')'){
					System.out.println("in 3");
					while(!operations.isEmpty()&&operations.peek()!='('){
						answer+=String.valueOf(operations.pop())+" ";
					}
					if(operations.pop()!='('){
						throw new IllegalArgumentException("illegal exception");
					}
				}
				else{
					System.out.println("in 4");
					answer+=operations.pop()+" ";
					operations.push(occurrence);
				}
			}
		}
		while(!operations.isEmpty()){
			answer+=operations.pop()+" ";
		}
		scanner.close();
		return answer;
	}
	
	public static void main(String args[]){
		
		//System.out.println(evaluate("(((2+3)+3)*3)"));
		//System.out.println("concequence:"+evaluatePostfix("2 3.0*5-6/"));
		String midExpression="2";
		String postExpression=priorityOfMid(midExpression);
		System.out.println("postExpression:"+postExpression);
		
		System.out.print(midExpression+"=");
		double x=evaluatePostfix(postExpression);
		
		System.out.println(x);
	}
}