简单算术表达式求值

简单算术表达式求值(仅含() 与+ - * /)

定义一个栈Stack类

public class Stack<E> implements Iterable<E>{
    private LinkedList<E> stack;

    public Stack() {
        this.stack = new LinkedList<>();
    }

    public void push(E e){
        stack.push(e);
    }

    public E pop(){
        return stack.pop();
    }

    public E peek(){
        return stack.peek();
    }

    public void each(Consumer<? super E> consumer){
        stack.stream().forEach(consumer);
    }

    public boolean isEmpty(){
        return stack.isEmpty();
    }

    public int size(){
        return stack.size();
    }

    @Override
    public Iterator<E> iterator() {
        return stack.iterator();
    }
}

1.中序表达式求值

/**
 * 1.创建2个栈: 操作数栈dataStack 操作符栈optStack
 * 2.从左至右一次扫描表达式
 * 3.遇到操作数时,压入dataStack
 * 4.遇到"+-/*"时与optStack栈顶操作符比较优先级,
 *   1).如果大于栈顶操作符优先级则入栈;
 *   2).如果小于等于栈顶操作符优先级,则取出optStack栈顶操作符
 *      与dataStack栈顶2个对应操作数,将计算结果存入dataStack;
 *   3).重复步骤1),2),直到比optStack栈顶元素优先级高时入栈;
 * 6.遇到括号时
 *   1).如果为"("则压入optStack;
 *   2).如果为")"则取出optStack栈顶操作符与dataStack栈顶2个对应操作数,
 *      将计算结果存入dataStack,重复此步骤,直到遇到"("停止,此时"("出栈丢弃
 * 7.扫描结束后依次取出optStack栈顶操作符与dataStack栈顶2个对应操作数,
 *   将计算结果存入dataStack,重复此步骤,直到optStack栈为空,
 *   此时dataStack(仅剩一个操作数)栈顶操作数即为计算结果
 */
@Test
public void expression(){
    String[] exp = {
            "( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )",
            "2 + 3 * 4 + 5",
            "100 * ( 2 + 12 )",
            "100 * ( 2 + 12 ) / 14",
            "(100/(3+7)+10)*(10-2)",
            "5+(3+5)/4*12",
            "5-2+3"
    };
    StringBuffer str = new StringBuffer(exp[6].replace(" ",""));
    System.out.println(str);
    char[] ch = str.toString().toCharArray();
    Stack<Character> optStack = new Stack<>();
    Stack<Integer> dataStack = new Stack<>();
    for(int i=0,len=ch.length;i<len;++i){
        if(ch[i] == '(')
            optStack.push(ch[i]);
        if("*/".contains(Character.toString(ch[i]))) {
            while(!optStack.isEmpty() && "*/".contains(Character.toString(optStack.peek()))){
                getResult(dataStack,optStack,optStack.peek());
            }
            optStack.push(ch[i]);
        }
        if("0123456789".contains(Character.toString(ch[i]))){
            String dig = ""+ch[i++];
            while(i<len && "0123456789".contains(Character.toString(ch[i]))){
                dig += ch[i++];
            }
            i--;
            dataStack.push(Integer.parseInt(dig));
        }
        if("+-".contains(Character.toString(ch[i]))){
            while(!optStack.isEmpty() && !"(".contains(optStack.peek().toString())) {
                getResult(dataStack,optStack,optStack.peek());
            }
            optStack.push(ch[i]);
        }
        if(')' == ch[i]){
            Character cur = null;
            while((cur = optStack.peek())!='('){
                getResult(dataStack,optStack,cur);
            }
            if(optStack.peek() == '(')
                optStack.pop();
        }
    }
    while(!optStack.isEmpty() && !dataStack.isEmpty())
        getResult(dataStack,optStack,optStack.peek());
        System.out.print(dataStack.pop()+ " ");
}


public void getResult(Stack<Integer> dataStack,Stack<Character> optStack,Character cur){
    optStack.pop();
    switch(cur){
        case '+':
            dataStack.push(dataStack.pop()+dataStack.pop());
            break;
        case '-':
            dataStack.push(-dataStack.pop()+dataStack.pop());
            break;
        case '*':
            dataStack.push(dataStack.pop()*dataStack.pop());
            break;
        case '/':
            Integer top = dataStack.pop();
            dataStack.push(dataStack.pop()/top);
            break;
        default:
            break;
    }
}

2.中序表达式转后序表达式再求值

中序表达式转后序表达式

    /**
     * 1.创建2个栈: 中间结果栈resultStack 与 操作符栈optStack
     * 2.从左至右扫描中序表达式
     * 3.遇到操作数时压入resultStack栈
     * 4.遇到运算符时,与optStack栈顶运算符进行比较
     *   1).如果栈顶元素为"("则压入resultStack栈
     *   2).如果大于栈顶运算符优先级则压入optStack栈
     *   3).如果小于等于栈顶运算符优先级,则取出optStack栈顶元素压入resultStack栈,
     *   4).重复步骤1),2),3)直到该运算符压入栈为止
     *  5.遇到括号时
     *   1).如果为"(",压入optStack
     *   2).如果为")"则取出optStack栈顶元素压入resultStack栈,重复此步骤直到遇到"("结束,此时丢弃"("
     *  6.扫描结束后将optStack栈中运算符压入resultStack栈
     *  7.依次弹出resultStack栈元素,结果的逆序即为对应的后序表达式
     */
    @Test
    public void backExpression(){
        String[] exp = {
                "( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )",
                "2 + 3 * 4 + 5",
                "100 * ( 2 + 12 )",
                "100 * ( 2 + 12 ) / 14",
                "(100/(3+7)+10)*(10-2)",
                "5+(3+5)/4*12",
                "5-2+3"
        };
        char[] ch = exp[0].replace(" ","").toCharArray();
        Stack<Character> optStack = new Stack<>();
        Stack<String> resultStack = new Stack<>();
        for(int i=0,len=ch.length;i<len;++i){
            String curChar = Character.toString(ch[i]);
            if('(' == ch[i])
                optStack.push(ch[i]);
            else if("*/".contains(curChar)){
                Character cur = null;
                while(!(optStack.isEmpty() || "(+-".contains((cur = optStack.peek()).toString()))){
                    Character curOpt = optStack.pop();
                    resultStack.push(curOpt+"");
                }
                optStack.push(ch[i]);
            }
            else if("+-".contains(curChar)){
                Character cur = null;
                while(!(optStack.isEmpty() || "(".contains((cur = optStack.peek()).toString()))){
                    Character curOpt = optStack.pop();
                    resultStack.push(curOpt+"");
                }
                optStack.push(ch[i]);
            }
            else if(')' == ch[i]){
                Character cur = null;
                while(!optStack.isEmpty() && '(' != (cur = optStack.pop())){
                    resultStack.push(cur+"");
                }
            }
            else if("0123456789".contains(curChar)){
                while(++i<ch.length && "0123456789".contains(Character.toString(ch[i]))){
                    curChar += ch[i];
                }
                resultStack.push(curChar);
                --i;
            }
            else{
                throw new RuntimeException("含有无法处理操作符");
            }
        }

        while(!optStack.isEmpty()){
            resultStack.push(optStack.pop()+"");
        }

        //生成后续表达式
        Stack<String> back = new Stack<>();
        while(!resultStack.isEmpty()){
            back.push(resultStack.pop());
        }
        //测试
        back.forEach(x -> System.out.print(x+" "));

        Double result = calcBackExpression(back);
        String resultStr = result+"";
        if(resultStr.length()-2 == resultStr.indexOf(".") && resultStr.charAt(resultStr.length()-1) =='0'){
            resultStr = resultStr.split("\\.")[0];
        }
        System.out.println(resultStr);
    }

后序表达式求值

    /**
     * 1.从左至右扫描后序表达式
     * 2.遇到操作数压入栈中
     * 3.遇到运算符,从栈中弹出2个对应操作数计算结果并压入该栈
     * 4.扫描到结尾栈中的值即为计算结果
     */
    public Double calcBackExpression(Stack<String> stack){
        Stack<Double> dataStack = new Stack<>();
        while(!stack.isEmpty()){
            String cur = stack.pop();
            if("+-*/".contains(cur)){
                switch(cur){
                    case "+":
                        dataStack.push(dataStack.pop()+dataStack.pop());
                        break;
                    case "-":
                        dataStack.push(-dataStack.pop()+dataStack.pop());
                        break;
                    case "*":
                        dataStack.push(dataStack.pop()*dataStack.pop());
                        break;
                    case "/":
                        dataStack.push(1/dataStack.pop()*dataStack.pop());
                        break;
                    default:
                        break;
                }
            }
            else{
                dataStack.push(Double.parseDouble(cur));
            }
        }

        return dataStack.pop();
    }

3.中序表达式转前序表达式再求值

中序表达式转前序表达式

    /**
     * 1.创建2个栈: 中间结果栈resultStack 与 操作符栈optStack
     * 2.从右至左扫描中序表达式
     * 3.遇到操作数压入resultStack栈
     * 4.遇到操作符时与optStack栈顶元素优先级进行比较
     *  1).如果栈顶元素为")",则压入optStack栈
     *  2).如果优先级大于等于栈顶元素,则压入optStack栈;
     *  3).如果优先级小于栈顶元素,则弹出optStack栈顶元素压入resultStack栈;
     *  4).重复步骤1),2),3)直到该操作符压入栈为止
     * 5.遇到括号时
     *  1).如果为")",则压入optStack栈;
     *  2).如果为"(",则依次弹出optStack栈顶元素压入resultStack栈,直到遇到")"为止,此时丢弃"(";
     * 6.扫描结束后,依次弹出optStack栈中操作符压入resultStack栈
     * 7.依次弹出resultStack栈元素,其结果即为前序表达式
     */
    @Test
    public void preOrderExpression(){
        String[] exp = {
                "( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )",
                "2 + 3 * 4 + 5",
                "100 * ( 2 + 12 )",
                "100 * ( 2 + 12 ) / 14",
                "(100/(3+7)+10)*(10-2)",
                "5+(3+5)/4*12",
                "5-2+3"
        };
        char[] ch = exp[0].replace(" ","").toCharArray();
        Stack<Character> optStack = new Stack<>();
        Stack<String> resultStack = new Stack<>();
        for(int i=ch.length-1;i>=0;--i){
            Character cur = ch[i];
            if(')' == cur || "/*".contains(cur+""))
                optStack.push(cur);
            else if("+-".contains(Character.toString(cur))){
                while(!optStack.isEmpty() && "/*".contains(optStack.peek()+"")){
                    resultStack.push(optStack.pop()+"");
                }
                optStack.push(cur);
            }
            else if("0123456789".contains(Character.toString(cur))){
                String temp = cur+"";
                while(--i >= 0 && "0123456789".contains(ch[i]+"")){
                    temp += ch[i];
                }
                resultStack.push(new StringBuilder(temp).reverse().toString());
                ++i;
            }
            else if('(' == cur){
                while(!optStack.isEmpty() && ')' != optStack.peek()){
                    resultStack.push(optStack.pop()+"");
                }
                optStack.pop();
            }
            else{
                throw new RuntimeException("未知运算符");
            }
        }

        while(!optStack.isEmpty())
            resultStack.push(optStack.pop()+"");

        Stack<String> preOrder = new Stack<>();
        //resultStack.forEach(x -> System.out.print(x+" "));
        while(!resultStack.isEmpty())
            preOrder.push(resultStack.pop());
        //preOrder.forEach(x -> System.out.print(x+" "));
        System.out.print(calcPreOrder(preOrder));
    }

前序表达式求值

    /**
     * 1.从右至左扫描前序表达式
     * 2.遇到操作数压入栈
     * 3.遇到运算符时从栈中弹出2个对应操作数并将计算结果入栈
     *   注意: 依次弹出a1 a2 ,若运算符为"-"则计算为 a1-a2, 如果为"/" 为a1/a2
     * 4.扫描结束后栈中的值即为前序表达式值
     */
    public Double calcPreOrder(Stack<String> stack){
        Stack<Double> dataStack = new Stack<>();
        while(!stack.isEmpty()){
            String cur = stack.pop();
            if("+-*/".contains(cur)){
                switch(cur){
                    case "+":
                        dataStack.push(dataStack.pop()+dataStack.pop());
                        break;
                    case "-":
                        dataStack.push(dataStack.pop()-dataStack.pop());
                        break;
                    case "*":
                        dataStack.push(dataStack.pop()*dataStack.pop());
                        break;
                    case "/":
                        dataStack.push(dataStack.pop()/dataStack.pop());
                        break;
                    default:
                        break;
                }
            }
            else{
                dataStack.push(Double.parseDouble(cur));
            }
        }

        return dataStack.pop();
    }