算法学习：完整的表达式括号匹配算法

《算法4》课后题目中，有一道题：编写一道程序，从标准输入得到一个缺少左括号的表达式并打印出补全括号之后的中序表达式。例如，给定输入： 1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) ) 你的程序应该输出： ((1 + 2) * ((3 - 4) * (5 - 6)))

网上有关这道题目，实现的基本都是左括号匹配，对于右括号匹配，未能找到答案。并且，如果考虑操作符优先级的话，题目给出的预期结果，也只是其中一种结果，还有其他的匹配结果。

于是自己实现一个算法，匹配左右括号，而且带操作符优先级。代码如下，供大家学习参考。

package com.sylar;

import java.util.Stack;

/**
 * 表达式括号匹配
 *
 * 编写一道程序，从标准输入得到一个缺少左括号的表达式并打印出补全括号之后的中序表达式。
 * 例如，给定输入： 1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )
 * 你的程序应该输出： ((1 + 2) * ((3 - 4) * (5 - 6)))
 */
public class ExpressBracketMatch {

    //操作符优先级定义
    final static String OPERATOR_PRIORITY[] = new String[]{"+-", "*/", "^"};

    //需要考虑操作符优先级
    private boolean needPriority = true;

    public ExpressBracketMatch(){
        this.needPriority = true;
    }

    public ExpressBracketMatch(boolean needPriority){
        this.needPriority = needPriority;
    }

    /**
     * 表达式匹配
     *
     * @param express 表达式参数，可以包含空白
     * @return
     */
    public String autoMatch(String express) {
        String newExpress = express.replaceAll("\\s", "");
        Stack<String> operStack = new Stack<>();
        Stack<String> dataStack = new Stack<>();

        for (int i = 0; i < newExpress.length(); i++) {
            String ss = String.valueOf( newExpress.charAt(i) );
            if (isDigit(ss.charAt(0))) {
                //处理数字的情况
                dataStack.push(ss);
            } else if ( isOperator(ss.charAt(0) ) ) {
                if(false == this.needPriority){
                    operStack.push(ss);
                    continue;
                }
                //处理操作符
                if (operStack.isEmpty()) {
                    operStack.push(ss);
                } else {
                    //操作符优先级处理
                    doMatch(dataStack, operStack, ss.charAt(0));
                }
            } else if( "(".equals(ss) ) {
                operStack.push(ss);
            } else {
                // 处理右括号的情况
                doMatch(dataStack, operStack);
            }
        }

        while (operStack.size() > 0) {
            String preOp = operStack.peek();
            if( "(".equals(preOp) ){
                operStack.pop();
                continue;
            }
            doMatch(dataStack, operStack);
        }

        return dataStack.pop();
    }

    /**
     * 匹配括号
     *
     * @param dataStack 操作数栈
     * @param operStack 操作符栈
     */
    private void doMatch(Stack<String> dataStack, Stack<String> operStack ){
        if(operStack.isEmpty()){
            return;
        }

        String right = dataStack.pop();
        String left = dataStack.pop();
        String opt = operStack.pop();
        String bracket = ")";
        if( !operStack.isEmpty() && operStack.peek().equals(")") ){
            operStack.pop();
        }
        dataStack.push("(" + left + opt + right + bracket);
    }

    /**
     * 匹配括号，处理优先级
     *
     * @param dataStack 操作数栈
     * @param operStack 操作符栈
     * @param curOper 当前操作符
     */
    private void doMatch(Stack<String> dataStack, Stack<String> operStack, char curOper ){
        if( operStack.isEmpty() ){
            operStack.push( String.valueOf(curOper) );
            return;
        }

        String preOp = operStack.peek();
        if ( preOp.equals("(") ) {
            operStack.pop();
            operStack.push( String.valueOf(curOper) );
            return;
        }

        if (getPriority(preOp.charAt(0)) >= getPriority(curOper)) {
            String right = dataStack.pop();
            String left = dataStack.pop();
            String opt = operStack.pop();
            String bracket = ")";
            if ( !operStack.isEmpty() && operStack.peek().equals(")") ) {
                operStack.pop();
            }
            dataStack.push("(" + left + opt + right + bracket);
            doMatch(dataStack, operStack, curOper);
        }else{
            operStack.push(String.valueOf(curOper));
        }
    }

    /**
     * 是否数字
     *
     * @param ch 数字参数
     * @return
     */
    private boolean isDigit(char ch) {
        return ch >= '0' && ch <= '9';
    }

    /**
     * 是否操作符
     *
     * @param op 操作符
     * @return
     */
    private boolean isOperator(char op){
        for(String ops : OPERATOR_PRIORITY ){
            if( ops.indexOf(op) != -1 ) {
                return true;
            }
        }
        return false;
    }

    /**
     * 获取操作符优先级
     *
     * @param op 操作符
     * @return
     */
    private int getPriority(char op){
        for( int i = 0; i < OPERATOR_PRIORITY.length; ++i ){
            if( OPERATOR_PRIORITY[i].indexOf(op) != -1 ){
                return i;
            }
        }
        throw new RuntimeException( new Exception("don't support operator: " + op) );
    }
}

基于JUnit4的测试用例，一并附上。上述代码功能还不完善，比如只能处理各位数字，不能处理函数（比如sqrt）等等。

package com.sylar;

import org.junit.Assert;
import org.junit.Test;

public class ExpressBracketMatchTest {

    @Test
    public void bracketTest0() {
        String result = new ExpressBracketMatch().autoMatch("1+2");
        Assert.assertEquals("(1+2)", result);
    }

    @Test
    public void bracketTest1() {
        String result = new ExpressBracketMatch().autoMatch("1+3*4+5");
        Assert.assertEquals("((1+(3*4))+5)", result);
    }

    @Test
    public void bracketTest2() {
        String result = new ExpressBracketMatch().autoMatch("((1+3)*2");
        Assert.assertEquals("((1+3)*2)", result);
    }

    @Test
    public void bracketTest3() {
        String result = new ExpressBracketMatch().autoMatch("(((1+3)*2-3");
        Assert.assertEquals("(((1+3)*2)-3)", result);
    }

    @Test
    public void bracketTest4() {
        String result = new ExpressBracketMatch().autoMatch("1/2/3+3");
        Assert.assertEquals("(((1/2)/3)+3)", result);
    }

    @Test
    public void bracketTest5() {
        String result = new ExpressBracketMatch().autoMatch("1/2/3+3*4");
        Assert.assertEquals("(((1/2)/3)+(3*4))", result);
    }

    @Test
    public void bracketTest6() {
        String result = new ExpressBracketMatch().autoMatch("1/(2/3)+3*5");
        Assert.assertEquals("((1/(2/3))+(3*5))", result);
    }

    @Test
    public void bracketTest7() {
        String result = new ExpressBracketMatch().autoMatch("1/(2/3)+3*5^3");
        Assert.assertEquals("((1/(2/3))+(3*(5^3)))", result);
    }

    @Test
    public void bracketTest8() {
        //((1 + 2)*((3 - 4)*(5-6)))
        String result = new ExpressBracketMatch().autoMatch("1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )");
        Assert.assertEquals("(((((1+2)*3)-4)*5)-6)", result);
    }

    @Test
    public void bracketTest9() {
        //((1 + 2)*((3 - 4)*(5-6)))
        String result = new ExpressBracketMatch(false).autoMatch("1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )");
        Assert.assertEquals("((1+2)*((3-4)*(5-6)))", result);
    }
}