使用后缀转换和评估的Java计算器

Question

我正在尝试创建一个程序，将infix表达式转换为后缀(使用堆栈)，并计算后缀表达式的结果。我已经有了一个可行的解决方案，但我觉得它很难看，而且必须有一个更好的方法。

(注意:程序必须能够接受大于9的数字和十进制数，所以它比通常的转换器要复杂一些)

Converter类：

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;


public class PostFixConverter {
    private String infix; // The infix expression to be converted
    private Deque<Character> stack = new ArrayDeque<Character>();
    private List<String> postfix = new ArrayList<String>(); // To hold the postfix expression

    public PostFixConverter(String expression)
    {
        infix = expression;
        convertExpression();
    }

    /* The approach is basically, if it's a number, push it to postfix list
     * else if it's an operator, push it to stack
     */
    private void convertExpression()
    {
        // Temporary string to hold the number
        StringBuilder temp = new StringBuilder();

        for(int i = 0; i != infix.length(); ++i)
        {           
            if(Character.isDigit(infix.charAt(i)))
            {
                /* If we encounter a digit, read all digit next to it and append to temp
                 * until we encounter an operator.
                 */
                temp.append(infix.charAt(i));

                while((i+1) != infix.length() && (Character.isDigit(infix.charAt(i+1)) 
                                                  || infix.charAt(i+1) == '.'))
                {
                    temp.append(infix.charAt(++i));
                }


                /* If the loop ends it means the next token is an operator or end of expression
                 * so we put temp into the postfix list and clear temp for next use
                 */
                postfix.add(temp.toString());
                temp.delete(0, temp.length());
            }
            // Getting here means the token is an operator
            else
                inputToStack(infix.charAt(i));
        }
        clearStack();
    }


    private void inputToStack(char input)
    {
        if(stack.isEmpty() || input == '(')
            stack.addLast(input);
        else 
        {
            if(input == ')')
            {
                while(!stack.getLast().equals('('))
                {
                    postfix.add(stack.removeLast().toString());
                }
                stack.removeLast();
            }
            else 
            {
                if(stack.getLast().equals('('))
                    stack.addLast(input);
                else
                {
                    while(!stack.isEmpty() && !stack.getLast().equals('(') && 
                            getPrecedence(input) <= getPrecedence(stack.getLast()))
                    {
                        postfix.add(stack.removeLast().toString());
                    }
                    stack.addLast(input);
                }
            }
        }
    }


    private int getPrecedence(char op)
    {
         if (op == '+' || op == '-')
                return 1;
         else if (op == '*' || op == '/')
                return 2;
         else if (op == '^')
                return 3;
         else return 0;
    }


    private void clearStack()
    {
        while(!stack.isEmpty())
        {
            postfix.add(stack.removeLast().toString());
        }
    }


    public void printExpression()
    {
        for(String str : postfix)
        {
            System.out.print(str + ' ');
        }
    }


    public List<String> getPostfixAsList()
    {
        return postfix;
    }
}

计算器类：

import java.math.BigDecimal;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;


public class PostFixCalculator {
    private List<String> expression = new ArrayList<String>();
    private Deque<Double> stack = new ArrayDeque<Double>();

    public PostFixCalculator(List<String> postfix) {expression = postfix;}


    public BigDecimal result()
    {
        for(int i = 0; i != expression.size(); ++i)
        {
            // Determine if current element is digit or not
            if(Character.isDigit(expression.get(i).charAt(0)))
            {
                stack.addLast(Double.parseDouble(expression.get(i)));
            }
            else 
            {
                double tempResult = 0;
                double temp;

                switch(expression.get(i))
                {
                    case "+": temp = stack.removeLast();
                              tempResult = stack.removeLast() + temp;
                              break;

                    case "-": temp = stack.removeLast();
                              tempResult = stack.removeLast() - temp;
                              break;

                    case "*": temp = stack.removeLast();
                              tempResult = stack.removeLast() * temp;
                              break;

                    case "/": temp = stack.removeLast();
                              tempResult = stack.removeLast() / temp;
                              break;
                }
                stack.addLast(tempResult);
            }
        }
        return new BigDecimal(stack.removeLast()).setScale(3, BigDecimal.ROUND_HALF_UP);
    }
}

下面是程序的一些测试运行：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class ConsoleCalc {

    public static void main(String[] args) throws IOException
    {
        String expression;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("Enter expression: ");
        expression = br.readLine();

        PostFixConverter pc = new PostFixConverter(expression); 
        System.out.print("Postfix: "); 
        pc.printExpression();

        PostFixCalculator calc = new PostFixCalculator(pc.getPostfixAsList());
        System.out.println();
        System.out.println("Result: " + calc.result());
    }
}

结果：

输入表达式: 10.2*(8-6)/3+112.5后缀: 10.2 8 6-*3/ 112.5 +结果: 119.300

我特别关注转换器类中的convertExpression方法。我用临时StringBuilder逐个数字读取数字标记的方式真的很难看。

Answer 1

在语法分析器中常见的是将词法标记部分从语义语法分析中分离出来。您可以在unix解析器工具中看到这一点，这些工具有词法工具flex/lex和解析器工具bison/yacc。

我会考虑在您的代码中进行更大的分离。创建一个新的Token类来保存单个令牌，并创建一个新的Tokenizer类，其任务是将输入拆分为一个令牌列表。然后，解析器将处理令牌列表并生成堆栈。这样就可以更容易地识别bug，即词法部分或语法解析中的bug。它还将使代码的扩展更加容易。

在我的代码中，对于数字、运算符、变量名等，我有不同的Token子类。我使用正则表达式来匹配不同类型的令牌。我使用(\d+\.?\d*)|(\.\d+)来匹配数字。\d匹配单个数字，\d+匹配一个或多个十进制数字，\d*匹配零或多个数字，\.匹配文字小数点，\.?匹配可选小数点，(和)将子模式组合在一起，|匹配lhs或rhs。因此，lhs将匹配一组没有小数点位的数字，或一组后面跟着小数位和可选数字的数字。rhs将匹配小数位，后面是一组数字。这意味着整个regexp将匹配123,123,123.45，.45。