学步园

import java.util.Stack;

/**
 * 
 * Class PosfixParser.java
 * 
 * Description 利用堆栈原理，解析算术表达式求值。
 * 
 * Company mapbar
 * 
 * author Chenll E-mail:
 * 
 * Version 1.0
 * 
 * Date 2012-9-27 下午03:09:49
 */
public class PosfixParser {

	private static String expression = "1+4/(1+1)+2*(3+4)-6/3+5/(1/2+2/1)";
	// private static String expression = "(1+4)/2";
	private static Stack myStack = new Stack();


	//判断是否是操作数
	public boolean isOperand(char c) {
		char[] operators = { '+', '-', '*', '/', '(', ')' };
		for (int i = 0; i < operators.length; i++) {
			if (c == operators[i]) {
				return false;
			}
		}
		return true;
	}

	// 返回运算符的优先级
	private static int priority(char ch) {
		int priority;
		switch (ch) {
		case '+':
			priority = 1;
			break;
		case '-':
			priority = 1;
			break;
		case '*':
			priority = 2;
			break;
		case '/':
			priority = 2;
			break;
		case '(':
			priority = 0;
			break;
		default:
			priority = 0;
			break;
		}
		return priority;
	}

	// 对两个值利用运算符计算结果
	private static double GetValue(char op, double ch1, double ch2) {
		switch (op) {
		case '+':
			return ch2 + ch1;
		case '-':
			return ch2 - ch1;
		case '*':
			return ch2 * ch1;
		case '/':
			return ch2 / ch1;
		default:
			return 0;
		}
	}

	/**
	 * 算术表达式转换为后续表达式步骤：
	 * (1)从左向右依次取得数据ch  
	 * (2)如果ch是操作数，直接输出
	 * (3)如果ch是运算符（含左右括号），则：
	 * a：如果ch = '('，放入堆栈
	 * b：如果ch = ')'，依次输出堆栈中的运算符，直到遇到'('为止
	 * c：如果ch不是')'或者'('，那么就和堆栈顶点位置的运算符top做优先级比较 
	 * 1：如果ch优先级比top高，那么将ch放入堆栈
	 * 2：如果ch优先级低于或者等于top，那么输出top，然后将ch放入堆栈
	 *(4)如果表达式已经读取完成，而堆栈中还有运算符时，依次由顶端输出
	 * 
	 * @return
	 */
	public String parse() {
		StringBuilder posfixExpression = new StringBuilder();
		char[] chars = expression.toCharArray();// 数据必须小于10
		for (char c : chars) {
			if (isOperand(c)) {
				// 是操作数
				posfixExpression.append(c);
			} else if (c == '(') {
				myStack.push(c);
			} else if (c == ')') {
				// 全部出栈
				while (!myStack.isEmpty()) { // 不停地弹出堆栈中的内容，直到遇到'('
					char ch = (Character) myStack.pop();
					if (ch == '(') {
						break;
					} else {
						posfixExpression.append(ch);
					}
				}
			} else { // 操作符
				if (!myStack.isEmpty()) {
					do {
						char ch1 = (Character) myStack.pop();// 弹出栈顶元素
						if (priority(ch1) < priority(c)) { // 如果栈顶元素的优先级小于读取到的操作符
							myStack.push(ch1);// 将栈顶元素放回堆栈
							myStack.push(c);// 将读取到的操作符放回堆栈
							break;
						} else {// 如果栈顶元素的优先级比较高或者两者相等时
							posfixExpression.append(ch1); // 将栈顶元素弹出
							if (myStack.isEmpty()) {
								myStack.push(c); // 将读取到的操作符压入堆栈中
								break;
							}
						}
					} while (!myStack.isEmpty());
				} else {
					// 空栈，操作符直接压入
					myStack.push(c);
				}
			}
		}
		while (!myStack.isEmpty()) {
			posfixExpression.append(myStack.pop()); // 将栈顶元素弹出//将堆栈中剩下的操作符输出
		}
		return posfixExpression.toString();
	}
	
	//由后续表达式求解表达式的值
	public double calcu(String posfixExpression){
		char[] chars = posfixExpression.toCharArray();
        myStack.clear();
        for(int i=0; i<chars.length; i++) {
        	 char ch = chars[i];
             if(isOperand(ch)){//如果是操作数，直接压入栈
                 myStack.push(ch);
             }
             else { //如果是操作符，就弹出两个数字来进行运算
	            double  no1 = Double.parseDouble(myStack.pop().toString());
	            double no2 = Double.parseDouble(myStack.pop().toString());
                double ret = GetValue(ch, no1, no2);
                myStack.push(ret);//将结果压入栈
             }
        }
        return Double.parseDouble(myStack.pop().toString());//弹出最后的运算结果
	}

	public static void main(String[] args) {
		PosfixParser pfp = new PosfixParser();
		String express = pfp.parse();
		double result = pfp.calcu(express);
		System.out.println(result);
	}
}