中缀表达式转换成后缀表达式及后缀表达式的运算

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

/**
 * 四则运算 + - * / ()
 * 1、由中缀到后缀
 * 2、由后缀算结果
 * User: yfzhangbin
 * Date: 13-12-26
 * Time: 上午11:58
 */
public class Operation {

    private static Stack<Character> symbolStack = new Stack<Character>();
    private static Stack<Integer> numStack = new Stack<Integer>();
    private static Pattern numberPattern = Pattern.compile("\\d*"); // 匹配数字

    public static void main(String[] args) {
        String express = "425-32*2+(8-5*7)*9+1"; // "9+(3-1)*3+10/2";
        express = infixToPostfix(express);
        System.out.println(express);
        System.out.println(calculate(express));
    }

    /**
     * 中缀表达式转换成后缀表达式
     * @param express 中缀表达式
     * @return 后缀表达式
     */
    private static String infixToPostfix(String express) {
        boolean isSymbol = false;
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < express.length(); i ++) {
            char c = express.charAt(i);
            if (' ' == c) continue;
            Matcher matcher = numberPattern.matcher(Character.toString(c));
            if (matcher.matches()) {
                if (isSymbol) { // 用来分割数字和算数运算符，用空格隔开
                    result.append(" ");
                    isSymbol = false;
                }
                result.append(c);
            } else {
                isSymbol = true;
                if (symbolStack.size() == 0) {
                    symbolStack.push(c); // 插入第一个符号元素
                    continue;
                }
                if (')' == c) { 
                    // 栈顶元素若为')',则依次弹栈直到最近的'('被弹出
                    char top = symbolStack.pop();
                    while (top != '(' && symbolStack.size() > 0) {
                        result.append(" ").append(top);
                        top = symbolStack.pop();
                    }
                } else if ('+' == c || '-' == c) { 
                    // 插入元素若为低优先级的'+','-'时，则先弹出栈顶元素再入栈; 如果当前栈顶元素为'('时，直接入栈
                    char top = symbolStack.peek();
                    while (top != '(' && symbolStack.size() > 0) {
                        result.append(" ").append(symbolStack.pop());
                        if (symbolStack.size() > 0)
                            top = symbolStack.peek();
                    }
                    symbolStack.push(c);
                } else { // 字符为(,*,/时直接入栈
                    symbolStack.push(c);
                }
            }
        }
        while (symbolStack.size() > 0) {
            result.append(" ").append(symbolStack.pop());
        }
        return result.toString();
    }


    /**
     * 后缀表达式的运算
     * @param express 后缀表达式
     * @return 运算结果
     */
    private static int calculate(String express) {
        String[] parts = express.split(" ");
        for (String part : parts) {
            Matcher matcher = numberPattern.matcher(part);
            if (matcher.matches()) {
                numStack.push(Integer.parseInt(part));
            } else if (numStack.size() >= 2) {
                int n2 = numStack.pop();
                int n1 = numStack.pop();
                //System.out.println(n1 + part +n2); // 打印运算过程
                if ("*".equals(part)) {
                    numStack.push(n1 * n2);
                } else if ("/".equals(part)) {
                    numStack.push(n1 / n2);
                } else if ("+".equals(part)) {
                    numStack.push(n1 + n2);
                } else if ("-".equals(part)) {
                    numStack.push(n1 - n2);
                }
            }
        }
        return numStack.pop();
    }

}