binary-tree - 一元运算符、二叉表达式树和调车场算法

Question

我正在编写数学表达式求解器，它采用中缀表达式并求解它们，二叉表达式树和分流场都对我有好处（我什至解决了处理一元和三元运算符的问题）。遇到三角函数问题。当我写 45sin 或 (45)sin 或 (44+1)sin 时，调车场将其转换为有效的逆波兰表示法 (RPN) 并且评估成功。虽然有效的中缀表达式是 sin(44+1) 或 sin45 + 1。请建议解决这个问题。

这是 ExpressionEval 类中的 java 代码，它将中缀转换为 RPN。

public String infixToPostFix2(String[] expression)
{
    String val = "";

    if (expression == null || expression.length <= 0)
    return "";

    Stack<String> stack = new Stack<String>();
    ArrayList<String> exp = new ArrayList<String>();

    for (String token : expression)
    {
        if (OperatorList.isOperator(token))
        {
            Operator o1 = OperatorList.getOperator(token);
            Operator o2 = null;
            while (!stack.empty() && OperatorList.isOperator(stack.peek()))
            {
                o2 = OperatorList.getOperator(stack.peek());
                if (    (o1.getAssociativity() == Associativity.LEFT && o1.lessThanEqual(o2))
                    || (o1.getAssociativity() == Associativity.RIGHT && o1.lessThan(o2))
                    )
                {
                    exp.add(stack.pop());
                    continue;
                }
                break;
            }
            stack.push(token);
        }
        else if(OperatorList.isLeftParenthesis(token))
        {
            stack.push(token);
        }
        else if (OperatorList.isRightParentheis(token))
        {
            while(!OperatorList.isLeftParenthesis(stack.peek()))
            {
                if (stack.empty())
                {
                    this.error = Error.MISMATCHED_PARANTHESIS;
                    return ""; //Mismatched paranthesis
                }
                exp.add(stack.pop());
            }

            stack.pop();//Pop off the left paranthesis but not move to output
        }
        else //Operands
        {
            exp.add(token);
        }
        }

        while(!stack.empty())
        {
        String s = stack.pop();
        if (OperatorList.isParanthesis(s))
        {
            this.error = Error.MISMATCHED_PARANTHESIS;
            return "";
        }
        exp.add(s);
    }

    postfixExpression = new String[exp.size()];
    int index = 0;
    for (String elem : exp)
    {
    postfixExpression[index++] = elem;
    }

    CalcDebug.printArray(postfixExpression);

    return val;
}

一旦我们有了 post-fix 表达式，就会在 ExpressionEval 类的这个函数中完成评估

 public double evaluateExpression(String[] postfixExpression) {

    CalcDebug.Debug("evaluateExpression()");

    double val = 0.0;
    if (postfixExpression == null || postfixExpression.length <= 0)
        return val;

    Stack<String> operationStack = new Stack<String>();

    CalcDebug.printArray(postfixExpression);

    for (String elem : postfixExpression) {

        CalcDebug.Debug("elem = " + elem);

        if (!OperatorList.isOperator(elem)) {
            operationStack.push(elem);
        } else {
            double arg0 = 0.0;
            double arg1 = 0.0;
            double arg2 = 0.0;

            OperatorType t = OperatorList.getOperatorType(elem);
            if (t == OperatorType.BINARY) {
                arg1 = Double.parseDouble(operationStack.pop());
                arg0 = Double.parseDouble(operationStack.pop());
                val = CalculatorBrain.performCalculation(elem, arg0, arg1);
            } else if (t == OperatorType.UNARY) {
                arg0 = Double.parseDouble(operationStack.pop());
                val = CalculatorBrain.performCalculation(elem, arg0);
            } else if (t == OperatorType.TERNARY) {
                arg2 = Double.parseDouble(operationStack.pop());
                arg1 = Double.parseDouble(operationStack.pop());
                arg0 = Double.parseDouble(operationStack.pop());
                val = CalculatorBrain.performCalculation(elem, arg0, arg1,
                        arg2);
            }
            operationStack.push(Double.toString(val));
        }

        CalcDebug.printStack(operationStack);
    }

    val = Double.parseDouble(operationStack.pop());

    CalcDebug.Debug("val = " + val);

    return val;
}

运算符类与此有些相似。

package com.studentscalculator;

import com.studentscalculator.OperatorComparator.OPERATOR_PRIORITY;

public class Operator
{

    public enum OperatorType
    {
        UNARY, BINARY, TERNARY
    }

    public enum Associativity
    {
        LEFT, RIGHT
    }

    private String operator;
    public String getOperator(){return operator;}
    public void setOperator(String operator){this.operator = operator;}

    private int order;
    public int getOrder(){return order;}
    public void setOrder(int order){this.order = order;}

    private OperatorType type;
    public OperatorType getType(){ return type; }
    public void setType(OperatorType type){ this.type = type; }

    private Associativity associativity;
    public Associativity getAssociativity(){ return associativity;}
    public void setAssociativity(Associativity associativity){ this.associativity = associativity; }

    //Constructors
    public Operator(String operator)
    {
        this.setOperator(operator);
        this.setOrder(OperatorList.getOperatorOrder(operator));
        this.setType(OperatorList.getOperatorType(operator));
        this.setAssociativity(OperatorList.getOperatorAssociativity(operator));
    }

    public Operator(String operator, int order)
    {
        this.setOperator(operator);
        this.setOrder(order);
        this.setType(OperatorList.getOperatorType(operator));
    }

    public Operator(String operator, int order, OperatorType t)
    {
       init(operator, order, t, Associativity.LEFT);
    }

    public Operator(String operator, int order, OperatorType t, Associativity a)
    {
       init(operator, order, t, a);
    }

    void init(String operator, int order, OperatorType t, Associativity a)
    {
        this.setOperator(operator);
        this.setOrder(order);
        this.setType(t);
        this.setAssociativity(a);
    }


    public boolean lessThanEqual(Operator arg0)
    {
        int val = -(this.order - arg0.order);
        if (val <= 0)
            return true;
        else
            return false;
    }

    public boolean lessThan(Operator arg0)
    {
        int val = -(this.order - arg0.order);
        if (val < 0)
            return true;
        else
            return false;
    }

    @Override
    public String toString()
    {
        String val = String.format("Operator = %s : Order %s", getOperator(), getOrder());
        return val;
    }

}