0

我正在编写一个通过迭代评估 LISP 表达式的程序。LISP 表达式如下：

将二加二在 LISP 中写为：(+ 2 2)。LISP 表达式 (* 5 4 3 2 1) 将被评估为五个阶乘。

为此，我使用了一堆双打队列。一个字符串被输入到求值器中，我取字符串中的每一项，评估它是运算符还是操作数。当我到达 '(' 我需要将当前级别队列推入堆栈并实例化一个新队列以继续评估。如果我到达 ')' 我需要从当前级别队列中获取运算符，然后评估每个该队列中的操作数直到它为空，此时我将新评估的操作数提供给堆栈中的下一个队列（通过弹出它，提供操作数，然后将其推回）。

当我到达 ')' 并尝试使用当前运算符评估当前级别操作数时，我的问题似乎出现了。我已经试了：

operand = operator + opQueue.poll();

但这只是将运算符的 double 值添加到操作数... :( 我知道我在这里遗漏了一些相对基本的东西，但是任何建议或建议将不胜感激。完整的代码如下。我相信问题出在在 main 之前结束。为了清楚起见，我包含了所有代码。

import java.util.Queue;
import java.util.LinkedList;
import java.util.Stack;

public class IterativeEvaluator
{ 
  private ExpressionScanner expression;

  public IterativeEvaluator (String expression)
  {
    this.expression = new ExpressionScanner(expression);
  }

  public double evaluate(Queue<Double> operandQueue)
  {
    Stack<Queue<Double>> myStack = new Stack<Queue<Double>>();

    char operator = ' ';
    double operand = 0.0;

    Queue<Double> opQueue = operandQueue;

    // write your code here to evaluate the LISP expression iteratively
    // you will need to use an explicit stack to push and pop context objects

    while(expression.hasNextOperand() || expression.hasNextOperator())
    {

        if(expression.hasNextOperand())
        {
            operand = expression.nextOperand();
            opQueue.offer((double)operand);
        }

        if(expression.hasNextOperator())
        {
            operator = expression.nextOperator();
            if(operator == '(')
            {
                myStack.push(opQueue);
                opQueue = new LinkedList<Double>();             
            }   
            if(operator != '(' && operator != ')')
                opQueue.offer((double)operator);
            if(operator == ')')
            {
                operator = ((char)(opQueue.remove().intValue()));

                while(opQueue.peek() != null)
                {
                    operand = operator + opQueue.poll();

                }

                opQueue = myStack.pop();
                if(opQueue != null)
                    opQueue.offer(operand);

            }

        }


    }

    return operand;

  }
  public static void main(String [] args)
  {
    String s =  
      "(+\t(- 6)\n\t(/\t(+ 3)\n\t\t(- \t(+ 1 1)\n\t\t\t3\n\t\t\t1)\n\t\t(*))\n\t(* 2 3 4))";  // = 16.5
    IterativeEvaluator myEvaluator = new IterativeEvaluator(s);
    System.out.println("Evaluating LISP Expression:\n" + s);
    System.out.println("Value is: " + myEvaluator.evaluate(null)); 
  }
}  /* 201340 */
4

1 回答 1

1

这是您的代码的改进版本，带有一些注释。我希望，它有帮助。如果您想拥有更多不同的运算符，您只需要扩展它。

public double evaluate(Queue<Double> operandQueue)
{
    // from http://docs.oracle.com/javase/7/docs/api/java/util/ArrayDeque.html
    // "This class is likely to be faster than Stack when used as a stack, ..."
    ArrayDeque<Queue<Double>> myStack = new ArrayDeque<>();

    char operator; // don't pre-initialize with nonsense value
    double operand = Double.NaN; // not used, NaN indicates if we have an error

    Queue<Double> opQueue = operandQueue;

    if(!expression.hasNextOperand() && !expression.hasNextOperand())
      // carefully decide what to do if the entire expression is empty
      throw new IllegalArgumentException("empty expression");

    // write your code here to evaluate the LISP expression iteratively
    // you will need to use an explicit stack to push and pop context objects
    while(expression.hasNextOperand() || expression.hasNextOperator())
    {
        if(expression.hasNextOperand())
        {
            operand = expression.nextOperand();
            opQueue.offer(operand); // cast unnecessary
        }
        else // expression.hasNextOperator() is implied here
        {
            operator = expression.nextOperator();
            if(operator == '(')
            {
                myStack.push(opQueue);
                opQueue = new LinkedList<Double>();             
            }   
            else if(operator != ')') // using <else> we know operator!='('
                opQueue.offer((double)operator);
            else // using <else> we know operator==')'
            {
                operator = ((char)(opQueue.remove().intValue()));
                // get the first operand, using 0.0 here would be disastrous
                // e.g. for multiplications
                operand = opQueue.poll();
                while(opQueue.peek() != null)
                {
                  switch(operator)
                  {
                    case '+': operand += opQueue.poll(); break;
                    case '*': operand *= opQueue.poll(); break;
                    // you got the idea ...
                  }
                }
                opQueue = myStack.pop();
                if(opQueue != null)
                    opQueue.offer(operand);
            }
        }
    }
    return operand;
}
于 2013-10-28T10:37:10.963 回答