中缀转后缀实现-查看文章

中缀转后缀实现

发表于:2023-12-26 17:48:10 分类:JAVA 阅读:182次

import java.util.*;

/**
 * @author ERSREDMA
 */

public class ReversePolandDemo {
    public static void main(String[] args) {
        Number result = ReversePoland.compute("1000/10+((2+8)*4)-10-10/100+0.1");
        System.out.println(result);
    }
}
class ReversePoland{
    public static String generate(String expression){
        Stack<StackEntity> s1 = new Stack<>();
        Stack<StackEntity> s2 = new Stack<>();
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            StackEntity stackEntity = new StackEntity(Character.toString(c));
            if(stackEntity.isOperator){
                do{
                    stackEntity = handlerOperator(stackEntity, s1, s2);
                }while (stackEntity!=null);
            }else{
                int endIndex = i;
                while (endIndex<expression.length()-1){
                    char next = expression.charAt(endIndex+1);
                    Operator operator = Operator.typeOf(Character.toString(next));
                    if(operator!=null){
                        break;
                    }else {
                        endIndex++;
                    }
                }
                if(i == endIndex){
                    //只有一个数字
                    s2.push(stackEntity);
                }else{
                    String substring = expression.substring(i, endIndex+1);
                    s2.push(new StackEntity(substring));
                    i = endIndex;
                }
            }
        }
        while (!s1.isEmpty()){
            s2.push(s1.pop());
        }
        List<String> resList = new ArrayList<>();
        while (!s2.isEmpty()){
            resList.add(s2.pop().item);
        }
        Collections.reverse(resList);
        return String.join(" ",resList);
    }

    public static Number compute(String expression){
        String reversePolandExpression = generate(expression);
        String[] items = reversePolandExpression.split(" ");
        Stack<StackEntity> stack = new Stack<>();
        for (String item : items) {
            StackEntity stackEntity = new StackEntity(item);
            if(stackEntity.isOperator){
                StackEntity a = stack.pop();
                StackEntity b = stack.pop();
                Number operation = Operator.operation(a.number, b.number, stackEntity.getOperator());
                stack.push(new StackEntity(operation.toString()));
            }else{
                stack.push(stackEntity);
            }
        }
        return stack.pop().number;
    }

    private static StackEntity handlerOperator(StackEntity stackEntity,Stack<StackEntity> s1,Stack<StackEntity> s2){
        if(stackEntity.getOperator().getPriority()==2){
            //遇到括号时:
            if(Operator.LEFT==stackEntity.getOperator()){
                //如果是左括号“(”,则直接压入s1。
                s1.push(stackEntity);
            }else{
                //如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃
                while (true){
                    StackEntity pop = s1.pop();
                    if(pop.getOperator()==Operator.LEFT){
                        break;
                    }else{
                        s2.push(pop);
                    }
                }
            }
            return null;
        }
        if(s1.isEmpty()||Operator.LEFT.getOp().equals(s1.peek().item)){
            //如果s1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
            s1.push(stackEntity);
        }else{
            if(stackEntity.getOperator().getPriority()>s1.peek().getOperator().getPriority()){
                //否则,若优先级比栈顶运算符的高,也将运算符压入s1;
                s1.push(stackEntity);
            }else{
                //否则,将s1栈顶的运算符弹出并压入到s2中,再次转到4.a与s1中新的栈顶运算符相比较;
                s2.push(s1.pop());
                return stackEntity;
            }
        }
        return null;
    }

    public static class StackEntity{
        private String item;
        private Number number;
        private boolean isNumber;
        private Operator operator;
        private boolean isOperator;
        public StackEntity(String item){
            this.item = item;
            this.operator = Operator.typeOf(item);
            if(this.operator!=null){
                this.isOperator = true;
            }else{
                this.number = Double.valueOf(item);
                this.isNumber = true;
            }
        }

        public Number getNumber() {
            return number;
        }

        public void setNumber(Number number) {
            this.number = number;
        }

        public boolean isNumber() {
            return isNumber;
        }

        public void setNumber(boolean number) {
            isNumber = number;
        }

        public Operator getOperator() {
            return operator;
        }

        public void setOperator(Operator operator) {
            this.operator = operator;
        }

        public boolean isOperator() {
            return isOperator;
        }

        public void setOperator(boolean operator) {
            isOperator = operator;
        }

        @Override
        public String toString() {
            return this.item;
        }
    }

}
enum Operator{
    ADDITION("+",0),
    SUBTRACTION("-",0),
    MULTIPLICATION("*",1),
    DIVISION("/",1),
    LEFT("(",2),
    RIGHT(")",2);
    private String op;
    private int priority;
    Operator(String op,int priority){
        this.op = op;
        this.priority = priority;
    }

    public static Operator typeOf(String op){
        for (Operator value : values()) {
            if(value.getOp().equals(op)){
                return value;
            }
        }
        return null;
    }

    public String getOp() {
        return op;
    }

    public int getPriority() {
        return priority;
    }

    public static Number operation(Number a, Number b,Operator operator){
        switch (operator){
            case ADDITION:
                return a.doubleValue()+b.doubleValue();
            case SUBTRACTION:
                return b.doubleValue()-a.doubleValue();
            case MULTIPLICATION:
                return a.doubleValue()*b.doubleValue();
            case DIVISION:
                return b.doubleValue()/a.doubleValue();
            default:
                throw new RuntimeException("NOT SUPPORT:"+operator.op);
        }
    }
}


关键词:中缀转后缀


验证码: