哪种数据结构适合求解方程

Question

我计划从基础开发一个方程求解器，并且能够使用以下代码进行基本的数学运算。我使用了一个令牌堆栈结构，用于存储分隔符和数字令牌。虽然这个实现太基础了，但我想在以后的版本中改进它。我只需要一些帮助我使用数据结构将令牌存储为一组堆栈的方式。如有错误请指出？

import java.util.ArrayList;
import java.util.Stack;

class TokenStack<N, D> {
    private Stack<N> numberStack;
    private Stack<D> delimStack;

    public TokenStack() {
        numberStack = new Stack<N>();
        delimStack = new Stack<D>();
    }

    public void pushN(N num) {
        numberStack.push(num);
    }

    public N popN() {
        return numberStack.pop();
    }

    public void pushD(D delim) {
        delimStack.push(delim);
    }

    public D popD() {
        return delimStack.pop();
    }

    public boolean isEmptyN() {
        return numberStack.isEmpty();
    }

    public boolean isEmptyD() {
        return delimStack.isEmpty();
    }


}


public class GeneralST {
    private static final char SPACE_DELIM = ' ';
    private static final char ADD_DELIM = '+';
    private static final char SUB_DELIM = '-';
    private static final char MUL_DELIM = '*';
    private static final char DIV_DELIM = '/';
    protected static final char EQU_DELIM = '=';

    private TokenStack<String, Character> tokens = new TokenStack<String, Character>();
    protected ArrayList<Character> acceptedDelims = new ArrayList<Character>();
    protected ArrayList<Character> mathsDelims = new ArrayList<Character>();
    protected double result;


    public double getResult() {
        return result;
    }

    protected void setupDelims() {
        acceptedDelims.add(SPACE_DELIM);
        mathsDelims.add(ADD_DELIM);
        mathsDelims.add(SUB_DELIM);
        mathsDelims.add(MUL_DELIM);
        mathsDelims.add(DIV_DELIM);
        acceptedDelims.addAll(mathsDelims);
    }

    private void tokenize(String str) {
        String reverse = "";

        for (int i = str.length() - 1; i >= 0; i--) {
            char charAt = str.charAt(i);
            if (i > 1) {
                char charPre = str.charAt(i - 1);
                if (acceptedDelims.indexOf(charAt) == -1 && (charPre == '-' ||  charPre == '+')) {
                    reverse = reverse +  charPre + charAt;
                    i--;
                } else {
                    reverse = reverse + charAt;
                }
            } else {
                reverse = reverse + charAt;
            }

        }

        int i = 0;

        while (reverse.length() > 2) {
            char charAt = reverse.charAt(i);
            char chartNext = reverse.charAt(i + 1);
            if (acceptedDelims.indexOf(charAt) != -1 && acceptedDelims.indexOf(chartNext) != -1) {
                String previous = reverse.substring(0, i);
                if (!previous.equals("") && !previous.equals(" ")) {
                    tokens.pushN(previous);
                }

                if (mathsDelims.indexOf(charAt) != -1) {
                    tokens.pushD(charAt);
                }
                reverse = reverse.substring(i + 1);
                i = i - previous.length() - 1;
            }
            i++;
        }
        if (!reverse.equals("")) {
            tokens.pushN(reverse);
        }

    }

    private double equate() {

        double val = 0;
        int step = 1;
        int side = 1;
        while (!tokens.isEmptyN() && !tokens.isEmptyD()) {
            char delim = tokens.popD();
            double val1 = Double.valueOf(tokens.popN());
            double val2 = side * Double.valueOf(tokens.popN());
            switch (delim) {
                case ADD_DELIM:
                    val = val1 + val2;
                    break;

                case SUB_DELIM:
                    val = val1 - val2;
                    break;

                case MUL_DELIM:
                    val = val1 * val2;
                    break;

                case DIV_DELIM:
                    try {
                        val = val1 / val2;
                        break;
                    } catch (Exception exception) {
                        exception.printStackTrace();
                        break;
                    }

                case EQU_DELIM:
                    val = val1 - val2;
                    side = -1;
                    delim = '-';

            }
            String outString = "Step %d : %s %c %s = %f";
            String printString = String.format(outString, step, val1, delim, val2, val);
            step++;
            System.out.println(printString);
            tokens.pushN(String.valueOf(val));
        }
        return val;
    }

    public GeneralST(String str) {
        System.out.println("--------------------------------------");
        System.out.println("[EXP] : " + str);
        setupDelims();
        tokenize(str);
        result = equate();
        System.out.println("--------------------------------------");

    }

    public void PrintResult() {
        System.out.println("Result = " + result);
    }


}

class EquateST extends GeneralST {
    public EquateST(String str) {
        super(str);
    }

    @Override
    protected void setupDelims() {
        mathsDelims.add(EQU_DELIM);
        super.setupDelims();
    }

    public void PrintResult() {
        if (result == 0) {
            System.out.println("Result = True");
        } else {
            System.out.println("Result = False");
        }
    }


}


class Main {

    public static void main(String[] args) {
        String[] equations = {"6 + 2 + -4 * 4 - 5", "6 + 2 - 4 * 4 = -5", "6 + -2 - 4 = 4 - 5"};
        calculate(equations);

    }

    private static void calculate(String... equations)
    {
        for (String equation : equations) {
            if (equation.contains("=")) {
                EquateST equateST = new EquateST(equation);
                equateST.PrintResult();
            } else {
                GeneralST generalST = new GeneralST(equation);
                generalST.PrintResult();

            }

        }
    }
}

示例结果

--------------------------------------
[EXP] : 6 + 2 + -4 * 4 - 5
Step 1 : 6.0 + 2.0 = 8.000000
Step 2 : 8.0 + -4.0 = 4.000000
Step 3 : 4.0 * 4.0 = 16.000000
Step 4 : 16.0 - 5.0 = 11.000000
--------------------------------------
Result = 11.0
--------------------------------------
[EXP] : 6 + 2 - 4 * 4 = -5
Step 1 : 6.0 + 2.0 = 8.000000
Step 2 : 8.0 - 4.0 = 4.000000
Step 3 : 4.0 * 4.0 = 16.000000
Step 4 : 16.0 - -5.0 = 21.000000
--------------------------------------
Result = False
--------------------------------------
[EXP] : 6 + -2 - 4 = 4 - 5
Step 1 : 6.0 + -2.0 = 4.000000
Step 2 : 4.0 - 4.0 = 0.000000
Step 3 : 0.0 - 4.0 = -4.000000
Step 4 : -4.0 - -5.0 = 1.000000
--------------------------------------
Result = False

Answer 1

你的问题是"arithmetic evaluation"。

很多书中都提到了"Algorithm"。

解决它的最佳和简单方法：使用堆栈和 "postfix notation"。

你可以找到很多关于你最喜欢的编程语言的文章。

哪种数据结构适合求解方程

Which data structure is good for equation solving

java

linear-equation