Infix to后缀公式解析器Java

Question

我编写了一个程序，它将一个数学公式作为用户输入，并将其从infix转换为postfix。

它不支持负数。

该程序不依赖于用户必须注意如何使用空格，因此'1+2*3‘和'1 +2* 3’是相同的。(但像“x^2^3”这样的公式必须写成“x^(2^3)”)

它为以下操作符提供支持：+、-、*、/、^

最初，我已经完全自己编写了一个堆栈类，但是这一个 (堆栈类的学分由那个帖子的用户使用)更有用/更可重用，所以我更新了我的类。

import java.util.EmptyStackException;

public class MyStack<T> {
    private T[] data;
    private int numElements;

    public MyStack(int capacity) {
        data = newArray(capacity);
        numElements = 0;
    }

    private final T[] newArray(int capacity) {
        @SuppressWarnings("unchecked")
        T[] tmp = (T[]) new Object[capacity];
        return tmp;
    }

    private void enlarge() {
        T[] temp = data;
        data = newArray(temp.length * 2);
        System.arraycopy(temp, 0, data, 0, temp.length);
    }

    public void push(T element) {
        if (numElements == data.length) {
            enlarge();
        }
        else {
            data[numElements++] = element;
        }
    }

    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return data[numElements - 1];
    }

    public boolean isEmpty() {
        return (numElements == 0);
    }

    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return data[--numElements];
    }
}

下面是InfixToPostfix类本身：

import java.util.Scanner;

public class InfixToPostfix {

    //checks whether c is operator
    private static boolean isOperator(char c) {
        if (c == '+' || c == '-' || c == '*' || c == '/' ||
                c == '^' || c == '(' || c == ')') {
            return true;
        }
        else return false;
    }

    //compares precedence of topmost operator in stack with operator at current position in infix-string
    private static boolean isLowerPrecedence(char operatorOldChar, char operatorNewChar) {
        boolean check = true; //true = new operator has higher precedence than old operator; false = contrary
        int operatorOld = 0, operatorNew = 0; //will compare precedence of operators; higher number = higher precedence

        //assign precedence to old operator (topmost in stack)
        if (operatorOldChar == '+' || operatorOldChar == '-') operatorOld = 2;
        else if (operatorOldChar == '*' || operatorOldChar == '/') operatorOld = 3;
        else if (operatorOldChar == '^') operatorOld = 4;

        //assign precedence to new operator (current character in infix)
        if (operatorNewChar == '+' || operatorNewChar == '-') operatorNew = 2;
        else if (operatorNewChar == '*' || operatorNewChar == '/') operatorNew = 3;
        else if (operatorNewChar == '^') operatorNew = 4;

        if (operatorNewChar == '(') {
            check = false;
        }
        else if (operatorNewChar == ')') {
            check = true;
        }
        else if (operatorOld < operatorNew) {
            check = false;
        }
        else if (operatorOld >= operatorNew) {
            check = true;
        }

        return check;
    }

    public static String convertToPostfix(String infix) {
        MyStack<Character> stack = new MyStack<>(infix.length());
        StringBuilder postfix = new StringBuilder();
        boolean isStillOneNumber = true; //will differentiate between outputs like 11 or 1 1

        for (int i = 0; i < infix.length(); i++) {

            if (!isOperator(infix.charAt(i)) & infix.charAt(i) != ' ') { //handles numbers and constants
                if (isStillOneNumber) {
                    postfix.append(infix.charAt(i));
                }
                else {
                    postfix.append(" ");
                    postfix.append(infix.charAt(i));
                }
                isStillOneNumber = true;
            }

            else if (isOperator(infix.charAt(i))){ //handles operators
                if (infix.charAt(i) == ')') {
                    while (!stack.isEmpty() & stack.peek() != '(') {
                        postfix.append(" ");
                        postfix.append(stack.pop());
                    }
                    if (!stack.isEmpty()) {
                        stack.pop();
                    }
                }
                else {
                    if (!stack.isEmpty()) {
                        if (!isLowerPrecedence(stack.peek(), infix.charAt(i))) {
                            stack.push(infix.charAt(i));
                        }
                        else {
                            while (!stack.isEmpty()) {
                                postfix.append(" ");
                                postfix.append(stack.pop());
                            }
                            stack.push(infix.charAt(i));
                        }
                    }
                    else if (stack.isEmpty()) {
                        stack.push(infix.charAt(i));
                    }
                }
                isStillOneNumber = false;
            }

            else { //handles possible spaces in infix
                isStillOneNumber = false;
            }

        }
        while (!stack.isEmpty()) {
            postfix.append(" ");
            postfix.append(stack.pop());
        }
        return postfix.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter formula: ");
        String infix = scanner.nextLine();

        System.out.println(convertToPostfix(infix));

    }
}

我很想听听你对我的代码的意见！

Answer 1

标准栈

尝试使用像java.util.ArrayDeque这样的堆栈的标准实现。你在这里重新发明了轮子。

状态模式

介绍状态模式。我在这里给你举个例子。

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class NumberParser {


    public static void main(String[] args) {

        List<BigInteger> parse = new NumberParser("   10   22  32  ").parse();

        for (BigInteger bigInteger : parse) {
            System.out.println(bigInteger);
        }

    }


    private List<BigInteger> numbers;


    private final StringBuffer stringToParse;
    private final StringBuffer buffer;


    private State state;


    public NumberParser(String string) {
        this.stringToParse = new StringBuffer(string);
        this.buffer = new StringBuffer();
        this.setState(new Unknown());
    }


    private boolean hasCurrentChar() {
        return this.stringToParse.length() > 0;
    }


    private char removeCurrentChar() {
        if (hasCurrentChar()) {
            char ch = this.stringToParse.charAt(0);
            this.stringToParse.deleteCharAt(0);
            return ch;
        } else {
            throw new NoSuchElementException();
        }
    }

    private char currentChar() {
        if (this.stringToParse.length() > 0) {
            return this.stringToParse.charAt(0);
        } else {
            throw new NoSuchElementException();
        }
    }


    private void clearBuffer() {
        buffer.setLength(0);
    }


    private void recognizeNumber() {
        numbers.add(new BigInteger(buffer.toString()));
        clearBuffer();
    }


    public List<BigInteger> parse() {

        if (numbers == null) {

            this.numbers = new ArrayList<>();

            while (!(getState() instanceof End)) {
                getState().parse();
            }

        }

        return this.numbers;

    }


    private State getState() {
        return state;
    }


    private void setState(State state) {
        System.out.println(state.getStateInfo());
        this.state = state;
    }


    private interface State {
        public String getStateInfo();
        public void parse();
    }


    private interface End extends State {
    }


    private class Error implements End {

        @Override
        public String getStateInfo() {
            return "Something went wrong ...";
        }

        @Override
        public void parse() {
        }

    }


    private class NoMoreChars implements End {

        @Override
        public String getStateInfo() {
            return "No chars left.";
        }

        @Override
        public void parse() {
        }

    }


    private class RemoveWhiteSpaces implements State {

        @Override
        public String getStateInfo() {
            return "Removing white spaces.";
        }

        @Override
        public void parse() {

            if (hasCurrentChar()) {

                if (Character.isWhitespace(currentChar())) {
                    removeCurrentChar();
                } else {
                    setState(new Unknown());
                }

            } else {
                setState(new NoMoreChars());
            }

        }

    }


    private class Number implements State {

        @Override
        public String getStateInfo() {
            return "Parse digits.";
        }

        @Override
        public void parse() {

            if (hasCurrentChar()) {

                if (Character.isDigit(currentChar())) {
                    buffer.append(currentChar());
                    removeCurrentChar();
                } else {
                    recognizeNumber();
                    setState(new Unknown());
                }

            } else {
                recognizeNumber();
                setState(new NoMoreChars());
            }

        }

    }


    private class Unknown implements State {

        @Override
        public String getStateInfo() {
            return "Search ...";
        }

        @Override
        public void parse() {

            if (hasCurrentChar()) {

                if (Character.isWhitespace(currentChar())) {
                    setState(new RemoveWhiteSpaces());
                } else if (Character.isDigit(currentChar())){
                    setState(new Number());
                } else {
                    setState(new Error());
                }

            } else {
                setState(new NoMoreChars());
            }

        }

    }

}

此解析器搜索数字并返回它们。由于允许多次出现空白空间，所以空白空间中的数字是分开的。如果输入字母数字字符，机器将进入错误状态。

要点是避免嵌套if-语句，并且在解析过程中有明确的责任。此外，您的解决方案缺乏扩展性。如果出现新的需求，状态模式将帮助您以一种定义良好的方式管理它们。

首先，我建议有一个状态图。UML状态机是合适的。