ReversePolishType(逆波兰式算法解析)

Reverse polish type algorithm

逆波兰式算法

说的通俗一点就是把中叙表达式转为右叙表达式。举个例子他可以解析数学表达式。
假设一个数学表达式：56+78*(25+69/3)

他的中叙表达式：[56,+,78,*,(,25,+,69,/,3,)]

他的右叙表达式：[56,78,25,69,3,/,+,*,+]

看到有序表达式之后机器可以从左到右依次执行得到结果

那么问题就是要怎么把中叙表达式转化为右叙表达式：我花了蛮多的时间画出了逆波兰式算法的流程图：(画了好久求赞0.0)

最后提出Java实现：

public class Calculate {
    // 判断是否为操作符号
    public static boolean isOperator(String operator) {
        if (operator.equals("+") || operator.equals("-")
                || operator.equals("*") || operator.equals("/")
                || operator.equals("(") || operator.equals(")"))
            return true;
        else
            return false;
    }

    // 设置操作符号的优先级别
    public static int priority(String operator) {
        if (operator.equals("+") || operator.equals("-"))
            return 1;
        else if (operator.equals("*") || operator.equals("/"))
            return 2;
        else
            return 0;
    }

    // 做2值之间的计算
    public static String twoResult(String operator, String a, String b) {
        try {
            String op = operator;
            String rs = new String();
            double x = Double.parseDouble(b);
            double y = Double.parseDouble(a);
            double z = 0;
            if (op.equals("+"))
                z = x + y;
            else if (op.equals("-"))
                z = x - y;
            else if (op.equals("*"))
                z = x * y;
            else if (op.equals("/"))
                z = x / y;
            else
                z = 0;
            return rs + z;
        } catch (NumberFormatException e) {
            System.out.println("input has something wrong!");
            return "Error";
        }
    }
}

public class Expression {
    private ArrayList expression = new ArrayList();// 存储中序表达式

    private ArrayList right = new ArrayList();// 存储右序表达式

    private String result;// 结果

    // 依据输入信息创建对象，将数值与操作符放入ArrayList中
    private Expression(String input) {
        StringTokenizer st = new StringTokenizer(input, "+-*/()", true);
        while (st.hasMoreElements()) {
            String s=st.nextToken();
            expression.add(s);
        }
    }

    // 将中序表达式转换为右序表达式
    private void toRight() {
        Stacks aStack = new Stacks();
        String operator;
        int position = 0;
        while (true) {
            if (Calculate.isOperator((String) expression.get(position))) {
                if (aStack.top == -1
                        || ((String) expression.get(position)).equals("(")) {
                    aStack.push(expression.get(position));
                } else {
                    if (((String) expression.get(position)).equals(")")) {
                        while(true){

                            if (aStack.top != -1&&!((String) aStack.top()).equals("(")) {
                                operator = (String) aStack.pop();
                                right.add(operator);
                            }else{
                                if(aStack.top != -1)
                                    aStack.pop();
                                break;
                            }
                        }
                    } else {
                        while(true){
                            if (aStack.top != -1&&Calculate.priority((String) expression.get(position)) <= Calculate.priority((String) aStack.top())) {
                                operator = (String) aStack.pop();
                                if (!operator.equals("("))
                                    right.add(operator);
                            }else{
                                break;
                            }

                        }
                        aStack.push(expression.get(position));
                    }
                }
            } else
                right.add(expression.get(position));
            position++;
            if (position >= expression.size())
                break;
        }
        while (aStack.top != -1) {
            operator = (String) aStack.pop();
            if(!operator.equals("("))
                right.add(operator);
        }
    }

    // 对右序表达式进行求值
    private void getResult() {
        this.toRight();
        for(int i=0;i<right.size();i++){
            System.out.println(right.get(i));
        }
        Stacks aStack = new Stacks();
        String op1, op2, is = null;
        Iterator it = right.iterator();

        while (it.hasNext()) {
            is = (String) it.next();
            if (Calculate.isOperator(is)) {
                op1 = (String) aStack.pop();
                op2 = (String) aStack.pop();
                aStack.push(Calculate.twoResult(is, op1, op2));
            } else
                aStack.push(is);
        }
        result = (String) aStack.pop();
        it = expression.iterator();
        while (it.hasNext()) {
            System.out.print((String) it.next());
        }
        System.out.println("=" + result);
    }

    public static void main(String avg[]) {
        Expression boya = new Expression("56+78*(25+69/3)");
        boya.getResult();
    }
}

public class Stacks{
    private LinkedList list=new LinkedList();
    int top=-1;
    public void push(Object value){
        top++;
        list.addFirst(value);
    }
    public Object pop(){
        Object temp=list.getFirst();
        top--;
        list.removeFirst();
        return temp;

    }
    public Object top(){
        return list.getFirst();
    }
}

可能最近几天会贴一下Golang的实现。