java - Java 中的中缀到前缀数学表达式转换器

Question

我正在尝试编写一种将中缀数学表达式转换为前缀数学表达式的方法，为此我使用了堆栈。但在某些情况下我会遇到错误，并且我不知道问题出在哪里。

代码:

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Prefixer {

    public static void main(String[] args) {
        String fileName;
        boolean reduce = false;
        if (args.length == 1){
            fileName = args[0];
        }
        else if (args.length >= 2){
            reduce = args[0].equals("-r");
            fileName = args[1];
        }
        else
        {
            return;
        }
        BufferedReader reader;
        String line = "";
        try {
            reader = new BufferedReader(new FileReader (fileName));
            line = reader.readLine();
            line = line.trim();
        } catch (Exception e) {
            e.printStackTrace();
        }

        System.out.println(infixToPrefixConvert(line,reduce));
    }

    public static boolean isOperand(String s) {
        return !(s.equals("+") || s.equals("-") || s.equals("/") || s.equals("*") || s.equals("(") || s.equals(")"));
    }

    public static boolean isNumber(String s){
        try {
            Integer.parseInt(s.trim());
        } catch (Exception e){
            return false;
        }
        return true;
    }

    public static String operationCombine(Stack<String> operatorStack, Stack<String> operandStack, boolean reduce){
        String operator = operatorStack.pop();
        String rightOperand = operandStack.pop();
        String leftOperand = operandStack.pop();
        if (reduce && isNumber(rightOperand) && isNumber(leftOperand)){
            int left = Integer.parseInt(leftOperand);
            int right = Integer.parseInt(rightOperand);
            int result = 0;
            if (operator.equals("+")){
                result = left + right;
            }else if (operator.equals("-")){
                result = left - right;
            }else if (operator.equals("*")){
                result = left * right;
            }else if (operator.equals("/")){
                result = left / right;
            }
            return "" + result;

        }
        String operand = "(" + operator + " " + leftOperand + " "+ rightOperand + ")";
        return operand;
    }

    public static int rank(String s) {
        if (s.equals("+") || s.equals("-"))
            return 1;
        else if (s.equals("/") || s.equals("*"))
            return 2;
        else
            return 0;
    }

    public static String infixToPrefixConvert(String infix, boolean reduce) {
        Stack<String> operandStack = new Stack<String>();
        Stack<String> operatorStack = new Stack<String>();

        StringTokenizer tokenizer = new StringTokenizer(infix);
        while (tokenizer.hasMoreTokens()) {
            String token = tokenizer.nextToken();
            if (isOperand(token)) {
                operandStack.push(token);
            }

            else if (token.equals("(") || operatorStack.isEmpty()
                    || rank(token) > rank(operatorStack.peek())) {
                operatorStack.push(token);
            }

            else if (token.equals(")")) {
                while (!operatorStack.peek().equals("(")) {
                    operandStack.push(operationCombine(operatorStack, operandStack,reduce));
                }
                operatorStack.pop();
            }

            else if( rank(token) <= rank(operatorStack.peek())){
                while(!operatorStack.isEmpty() && rank(token) <= rank(operatorStack.peek())){
                    operandStack.push(operationCombine(operatorStack, operandStack,reduce));
                }
                operatorStack.push(token);
            }
        }
        while( !operatorStack.isEmpty() ) {
            operandStack.push(operationCombine(operatorStack, operandStack,reduce));
        }
        return (operandStack.peek());
    }

}

该文件的第一行应包含要转换的中缀表达式。如果您想在转换时减少简单的算术表达式，请使用 -r 标志为前缀。例如在 test.txt 中，如果我有

3 * 9 + ( 9 + y ) / 4 - x

它工作正常。但如果我有

12 / c + c * p ^ ( 8 + 9 )

它应该给我:12 c/c p 8 9 + ^ * +但我得到:(+ p (* ^ (+ 8 9)))

这是什么问题。请帮我。谢谢

Answer 1

只要看一眼你的代码，我可能会说这一行

String operand = "(" + operator + " " + leftOperand + " "+ rightOperand + ")";

这是问题的根源，事实上您没有在 operationCombine 函数中考虑运算符 ^ 。