Как сделать приоритет с несколькими экспонентами, ^, в арифметическом уравнении
Я работаю над программой, которая решает арифметические уравнения. Я столкнулся с проблемой, которая возникает, когда в строке несколько экспоненциальных операторов, программа не может их правильно решить. Примером может быть: 2 ^ 3 ^ 2, правильный ответ - 512, но программа выводит 64. Это потому, что программа делает 2 ^ 3, а затем 8 ^ 2 вместо 3 ^ 2, а затем 2^9. Дайте мне знать, если у вас есть идеи, как изменить мой текущий код или есть что добавить.
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");
}
}
}
2 ответа
Я решил бы это с Приоритетами оператора, поскольку вы могли бы хотеть иметь их так или иначе. Для тестирования я немного изменил класс, так что я мог проверить его, и он наверняка не самый эффективный или читаемый, но вы должны понять, как он работает.
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"));
}
}
Вы пытаетесь использовать грамматику LL(1) (что анализирует анализатор рекурсивного спуска) для моделирования правоассоциативного оператора (^). Правоассоциативный оператор требует левой рекурсии, которая не так легко работает с грамматикой LL(1). Вы захотите взглянуть на левый факторинг: http://en.wikipedia.org/wiki/LL_parser