我想了解我的家庭作業，JAVA Lisp的算術表達式

Question

我想確切地瞭解正在問我的是什麼，也許你可以給我一些直覺到如何看待解決這個問題。我需要用Java編寫一個程序來評估Lisp算術表達式，但解決方案必須遵循特定的指令。

我需要評估是這樣的：

(+\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)) 

我應該執行上下文棧，這

Stack<Queue<Double>> contextStack

，所以我猜測它是隊列的堆棧。我也有一類ExpressionScanner其掃描通過串並發現符和操作數：

public class ExpressionScanner 
{ 
    private String e; 
    private int position; 

    public ExpressionScanner(String e) 
    { 
    this.e = e; 
    this.position = 0; 
    } 


public boolean hasNextOperator() 
    { 
    skipWhiteSpace(); 
    return position < e.length() && isOperator(e.charAt(position)); 
    } 

    public char nextOperator() 
    { 
    skipWhiteSpace(); 
    return e.charAt(position++); 
    } 

    public boolean hasNextOperand() 
    { 
    skipWhiteSpace(); 
    return position < e.length() && isDigit(e.charAt(position)); 
    } 

    public int nextOperand() 
    { 
    skipWhiteSpace(); 
    int operand = 0; 
    while (e.charAt(position) >= '0' && e.charAt(position) <='9') 
     operand = 10 * operand + e.charAt(position++) - '0'; 
    return operand; 
    } 

    private void skipWhiteSpace() 
    { 
    char c; 
    while (position < e.length() && ((c = e.charAt(position)) == ' ' || c == '\t' || c == '\n')) 
     position++; 
    return; 
    } 

    private static boolean isOperator(char c) 
    { 
    return c == '(' || c == '+' || c == '-' || c == '*' || c == '/' || c == ')'; 
    } 

    private static boolean isDigit(char c) 
    { 
    return c >= '0' && c <= '9'; 
    } 
} /*201340*/ 

而這正是我的解決方案是應該進去，但我感到有點沮喪，因爲我不知道怎麼樣使用該堆棧隊列來實現解決方案。

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) 
    { 
     // write your code here to create an explicit context stack 

    char operator = ' '; 
     double operand = 0.0; 

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

    } 


    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 */ 

感謝您的任何幫助。

Answer 1

這是解決問題的辦法。

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


class IterativeEvaluator2 
{ 
    private ExpressionScanner expression; 

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

    public double evaluate(Queue<Double> operandqueue) 
    { 
      // write your code here to create an explicit context stack 
     Stack<Queue> temp_stack = new Stack<Queue>(); 

     char operator = ' '; 
      double operand = 0.0; 
     int a; 

      // 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.hasNextOperator() || expression.hasNextOperand()) 
     { 

      // Get the open bracket   

      if (expression.hasNextOperator())  
       { 
       operator = expression.nextOperator() ; 

       if (operator == '(') 
       { 
        temp_stack.push(operandqueue); 
        operandqueue = new LinkedList<Double>(); 
       } 

       // push the list into the stack after the closing bracket appears  
       else if (operator == ')') 
       { 
        if (operandqueue.size() > 1) { 
         //System.out.println("new opqueue"); 
         //System.out.println(operandqueue); 
         operand = calculate(operandqueue); 
         System.out.println(operand); 

         if (temp_stack.peek() != null) 
         { 
          operandqueue = temp_stack.pop(); 
         //System.out.println(operandqueue); 
          operandqueue.offer(operand); 
         } 
        } 
        else if (operandqueue.size() == 1) 
         operandqueue = temp_stack.pop(); 
       } 
      // if it is another operator then it must be +,-,/,* 
       else 
       { 
        operandqueue.offer((double) operator); 
       } 
      } 
      // else it is an operand so just put it in the queue 
      else 
      { 
       a= expression.nextOperand() ; 
       //System.out.println(a); 
       operandqueue.offer((double) a); 

      } 
     } 
     return operand; 
    } 

    private double calculate(Queue<Double> some_queue) 
    { 
      char operator = (char) some_queue.remove().intValue(); 
      //System.out.println(operator); 
      double operand1 = 0; 
      double operand2;    
      switch(operator){ 
      case '+' : while(!some_queue.isEmpty()) 
        { 
         operand2 = some_queue.remove(); 
         operand1 = operand1 + operand2; 
        } 
        break; 

      case '-' : operand1 = some_queue.remove(); 
        //checks for negative numbers 
        if (some_queue.isEmpty()){ 
         operand1 = 0 - operand1; 
         } 
        else{ 
         while (!some_queue.isEmpty()) 
         { 
          operand2 = some_queue.remove(); 
          operand1 = operand1 - operand2; 
          System.out.println(operand1); 
         } 

        } 
        break; 

      case '*' : if (!some_queue.isEmpty()) 
        { 
         operand1 = 1; 
         while (!some_queue.isEmpty()) 
         { 
          operand2 = some_queue.remove(); 
          operand1 = operand1*operand2; 
         } 
        } 
        break; 

      case '/' : operand1 = some_queue.remove(); 
        if (some_queue.isEmpty()) 
               operand1 = 1/operand1 ; 
            else{ 
              while (!some_queue.isEmpty()) 
         { 
           operand2 = some_queue.remove(); 
          operand1 = operand1/operand2;                        } 
        } 
        break; 
      } 
     return operand1; 
    } 

    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 
     IterativeEvaluator2 myEvaluator = new IterativeEvaluator2(s); 
     System.out.println("Evaluating LISP Expression:\n" + s); 
     System.out.println("Value is: " + myEvaluator.evaluate(null)); 
    } 
} /* 201340 */