java使用棧和逆波蘭表達式實作四則運算

Stack.java：

package calculator;

import java.util.LinkedList;

public class Stack {
	private LinkedList<String> stack = new LinkedList<String>();
	
	public void push(String str) {
		stack.push(str);
	}
	
	public String pop() {
		return stack.pop();
	}
	
	public boolean hasNext() {
		if(stack.isEmpty()) return false;
		return true;
	}
	
	public String peek() {
		return stack.peek();
	}
	
	public int size() {
		return stack.size();
	}
}
           

Calculator.java：

package calculator;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Calculator {
	private static Calculator calc = new Calculator();
	private Stack operatorStack = new Stack();   //操作符棧
	private Stack numStack = new Stack();	 //操作數棧
	
	public static void main(String[] args) {
		Calculator calculator = new Calculator();
		
 		String expression = "12+(5-2)*3-3*(4+1)";
 		System.out.println("expression: " + expression);
 		String suffixExpr = calculator.convert2SuffixExpression(expression);      //right result: 12 5 2 - 3 * + 3 4 1 + * -
 		System.out.println("\nright result: 12 5 2 - 3 * + 3 4 1 + * -");
 		System.out.println(suffixExpr);
 		
 		
 		String calcResult = calculator.calcResult(suffixExpr);
 		System.out.println("calcResult: " + calcResult);
	}
	
	private Calculator() {}
	
	public static Calculator getInstance() {
		return calc;
	}
	
	public int calc(String expression) {
		int result;
		try {
			result = Integer.parseInt(calc.calcResult(calc.convert2SuffixExpression(expression)));
		} catch (Exception e) {
			throw new RuntimeException("輸入不合法");
		}
		
		return result;
	}
	
	//轉換成字尾表達式
	private String convert2SuffixExpression(String expr) {
		StringBuffer buffer = new StringBuffer();
		
		String regex = "[\\+\\-\\*\\)\\(\\/]";
		Pattern p = Pattern.compile(regex);
		Matcher m = p.matcher(expr);
		while(m.find()) {
			m.appendReplacement(buffer, "#" + m.group() + "#");
		}
		m.appendTail(buffer);
		
		String[] strs = buffer.toString().split("#");
		StringBuffer output = new StringBuffer();
		for(String str : strs) {
			if(!"".equals(str) || null == str) {
//				System.out.print(str);
				
				if(str.matches("[0-9]+")) {   //數字
					output.append(str + " ");
				}
				else {                        //操作符
					if(str.equals(")")) {
						String s;
						while(!(s = operatorStack.pop()).equals("(")) {
							if(!s.equals("(")) {
								output.append(s + " ");
							}
						}
					}
					else {
						String top = operatorStack.peek();
						if(top != null) {
							if(("*".equals(top) || "/".equals(top)) && ("+".equals(str) || "-".equals(str))) {
								while(operatorStack.hasNext()) {
									output.append(operatorStack.pop() + " ");
								}
							}
						}
						operatorStack.push(str);
					}
				}
			}
		}
		
		//将操作符中剩餘内容append在最後
		while(operatorStack.hasNext()) {
			output.append(operatorStack.pop() + " ");
		}
		
		return output.toString();
	}
	
	
	//計算結果
	private String calcResult(String suffixExpr) {
		String[] strs = suffixExpr.split(" ");
		for(String str : strs) {
			if(str.matches("[0-9]+")) {    //數字則壓棧
				numStack.push(str);
			}
			else {                         //操作符則取出棧頂前兩個數字計算
				int num1 = Integer.parseInt(numStack.pop());
				int num2 = Integer.parseInt(numStack.pop());
				int result = calc(num2, num1, str);
				numStack.push(result + "");
			}
		}
//		System.out.println("numStack size: " + numStack.size());
		return numStack.pop();
	}
	
	private int calc(int a, int b, String oper) {
		if("+".equals(oper)) {
			return a + b;
		}
		if("-".equals(oper)) {
			return a - b;
		}
		if("*".equals(oper)) {
			return a * b;
		}
		if("/".equals(oper)) {
			return a / b;
		}
		throw new RuntimeException("operation error");
	}
}
           

Test.java：

package calculator;

public class Test {
	public static void main(String[] args) {
		Calculator calc = Calculator.getInstance();
		
		String expr1 = "(1+2)*3-6/2+1";
		System.out.println(calc.calc(expr1));
		
		String expr2 = "(5-2)*4-(3+1)/2";
		System.out.println(calc.calc(expr2));
		
		String errorExpr = "3+-2";
		System.out.println(calc.calc(errorExpr));
	}
}