如何做到优先与多个指数，^，算术等式

Question

我就可以解决的运算式的程序工作。我遇到了一个问题，当一行中有多个指数语句时，程序没有正确解决它们。一个例子是：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"); 
     } 
    } 

} 

Answer 1

你试图使用LL（1）语法（这是一个递归下降解析器可以解析）到右结合运算符（^）型号。甲右结合运算符需要左递归，不与LL（1）文法这样容易工作。你会想看看左保：http://en.wikipedia.org/wiki/LL_parser#Left_Factoring

Answer 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")); 
    } 

}