0

算術方程式を解くプログラムに取り組んでいます。複数の指数ステートメントが連続している場合に、プログラムがそれらを正しく解決しないという問題が発生しました。例: 2^3^2、正解は 512 ですが、プログラムは 64 を出力します。これは、プログラムが 3^2 の次に 2^9 を実行する代わりに、2^3 の次に 8^2 を実行するためです。現在のコードを変更する方法や何か追加する方法について何かアイデアがあれば教えてください。

import java.text.DecimalFormat;
import java.util.EmptyStackException;
import myUtil.*;

public class PostFixEvaluator extends Asg6
{
    public static class SyntaxErrorException extends Exception
    {
        SyntaxErrorException(String message)
        {
            super(message);
        }
    }

    private static final String operators = "+-*/^()";
    private AStack<Double> operandStack;

    private double evaluateOP(char op) throws Exception
    {
        double rightside = operandStack.pop();
        double leftside = operandStack.pop();
        double result = 0;
        if(op == '+')
        {
            result = leftside + rightside;
        }
        else if(op == '-')
        {
            result = leftside - rightside;
        }
        else if(op == '*')
        {
            result = leftside * rightside;
        }
        else if(op == '/')
        {
            if(rightside == 0)
            {
                throw new Exception("Can not divide by 0, the equation is undefined");
            }
            else
            {
                result = leftside / rightside;
            }
        }
        else if(op == '^')
        {
            result = Math.pow(leftside, rightside);
        }
        return result;
    }

    private boolean isOperator(char ch)
    {
        return operators.indexOf(ch) != -1;
    }

    public double evaluate(String exp) throws Exception
    {
        operandStack = new AStack<Double>();
        String[] tokens = exp.split("\\s+");
        try
        {
            for(String nextToken : tokens)
            {
                char firstChar = nextToken.charAt(0);
                if(Character.isDigit(firstChar))
                {
                    double value = Double.parseDouble(nextToken);
                    operandStack.push(value);
                }
                else if (isOperator(firstChar))
                {
                    double result = evaluateOP(firstChar);
                    operandStack.push(result);
                }
                else
                {
                    throw new Exception("Invalid character: " + firstChar);
                }
            }
            double answer = operandStack.pop();
            if(operandStack.empty())
            {
                return answer;
            }
            else
            {
                throw new Exception("Syntax Error: Stack should be empty");
            }
        }
        catch(EmptyStackException ex)
        {
            throw new Exception("Syntax Error: The stack is empty");
        }
    }

}
4

2 に答える 2

0

右結合演算子 ( ) をモデル化するために、 LL(1)文法 (再帰降下パーサーが解析できるもの)を使用しようとしています^。右結合演算子には左再帰が必要ですが、 LL(1)文法ではそう簡単には機能しません。左因数分解を見たいと思うでしょう: http://en.wikipedia.org/wiki/LL_parser#Left_Factoring

于 2013-10-29T20:23:05.363 に答える
0

とにかく優先度が必要な場合があるので、これを演算子の優先度で解決します。テストのためにクラスを少し変更したので、テストできましたが、最も効率的でも読みやすいものでもありませんが、それがどのように機能するかを理解する必要があります。

import java.text.DecimalFormat;
import java.util.EmptyStackException;

import java.util.*;

public class PostFixEvaluator
{
    public static class SyntaxErrorException extends Exception
    {
        SyntaxErrorException(String message)
        {
            super(message);
        }
    }

    private static final String operators = "+-*/^()";
    private static int[] operatorPriority = {1,1,2,2,3,10,10};
    private Stack<Double> operandStack;
    private Stack<Character> operatorStack;

    private double evaluateOP(char op) throws Exception
    {
        double rightside = operandStack.pop();
        double leftside = operandStack.pop();
        double result = 0;
        if(op == '+')
        {
            result = leftside + rightside;
        }
        else if(op == '-')
        {
            result = leftside - rightside;
        }
        else if(op == '*')
        {
            result = leftside * rightside;
        }
        else if(op == '/')
        {
            if(rightside == 0)
            {
                throw new Exception("Can not divide by 0, the equation is undefined");
            }
            else
            {
                result = leftside / rightside;
            }
        }
        else if(op == '^')
        {
            result = Math.pow(leftside, rightside);
        }
        return result;
    }

    private boolean isOperator(char ch)
    {
        return operators.indexOf(ch) != -1;
    }

    public double evaluate(String exp) throws Exception
    {
        operandStack = new Stack<Double>();
        operatorStack = new Stack<Character>();
        String[] tokens = exp.split("\\s+");
        try
        {
            for(String nextToken : tokens)
            {
                char firstChar = nextToken.charAt(0);
                if(Character.isDigit(firstChar))
                {
                    double value = Double.parseDouble(nextToken);
                    operandStack.push(value);
                }
                else if (isOperator(firstChar))
                {
                    // Try to evaluate the operators on the stack
                    while (!operatorStack.isEmpty())
                    {
                        char tmpOperator = operatorStack.pop();
                        // If Operator has higher Priority than the one before,
                        // Calculate it first if equal first calculate the second
                        // operator to get the ^ problem fixed
                        if (operatorPriority[operators.indexOf(firstChar)] >= operatorPriority[operators.indexOf(tmpOperator)])
                        {
                           operatorStack.push(tmpOperator);
                           // Operand has to be fetched first
                           break;
                        }
                        else
                        {
                            double result = evaluateOP(tmpOperator);
                            operandStack.push(result);
                        }
                    }
                    operatorStack.push(firstChar);
                }
                else
                {
                    throw new Exception("Invalid character: " + firstChar);
                }
            }

            // Here we need to calculate the operators left on the stack
            while (!operatorStack.isEmpty())
            {
                char tmpOperator = operatorStack.pop();
                // Operator Priority has to be descending,
                // or the code before is wrong.
                double result = evaluateOP(tmpOperator);
                operandStack.push(result);
            }

            double answer = operandStack.pop();
            if(operandStack.empty())
            {
                return answer;
            }
            else
            {
                throw new Exception("Syntax Error: Stack should be empty");
            }
        }
        catch(EmptyStackException ex)
        {
            throw new Exception("Syntax Error: The stack is empty");
        }
    }

    // For testing Only
    public static void main(String[] args) throws Exception
    {
        PostFixEvaluator e = new PostFixEvaluator();
        System.out.println(e.evaluate("2 ^ 3 ^ 2"));
    }

}
于 2013-10-29T20:23:18.037 に答える