Java的LISP實現幾乎工作

Question

package PJ2; 
import java.util.*; 

public class SimpleLispExpressionEvaluator 
{ 
    // Current input Lisp expression 
    private String inputExpr; 

    // Main expression stack & current operation stack, see algorithm in evaluate() 
    private Stack<Object> exprStack; 
    private Stack<Double> currentOpStack; 


    // default constructor 
    // set inputExpr to "" 
    // create stack objects 
    public SimpleLispExpressionEvaluator() 
    { 
    // add statements 
     inputExpr = ""; 
     exprStack = new Stack<Object>(); 
     currentOpStack = new Stack<Double>(); 
    } 

    // default constructor 
    // set inputExpr to inputExpression 
    // create stack objects 
    public SimpleLispExpressionEvaluator(String inputExpression) 
    { 
    // add statements 
     if(inputExpression == null) 
     { 
      throw new SimpleLispExpressionEvaluatorException(); 
     } 

     inputExpr = inputExpression; 
     exprStack = new Stack<Object>(); 
     currentOpStack = new Stack<Double>(); 

    } 

    // set inputExpr to inputExpression 
    // clear stack objects 
    public void reset(String inputExpression) 
    { 
    // add statements 
    if(inputExpression == null) 
    { 
     throw new SimpleLispExpressionEvaluatorException(); 
    } 

    inputExpr = inputExpression; 
    exprStack.clear(); 
    currentOpStack.clear(); 
    } 

    // This function evaluate current operator with its operands 
    // See complete algorithm in evaluate() 
    // 
    // Main Steps: 
    //  Pop operands from exprStack and push them onto 
    //   currentOpStack until you find an operator 
    //  Apply the operator to the operands on currentOpStack 
    //   Push the result into exprStack 
    // 
    private void evaluateCurrentOperation() 
    { 
    // add statements 
     String currOp; 
     boolean numeric = true; 
     do{ 
      currOp = (String.valueOf(exprStack.pop())); 

      try{ 
       Double number = Double.parseDouble(currOp); 
       currentOpStack.push(number); 

      }catch(NumberFormatException nfe){ 
       numeric = false; 
      } 
     } while(numeric); 


     double result; 
     switch (currOp) { 
      case "*": 
       result = currentOpStack.pop(); 
       while(!currentOpStack.isEmpty()){ 
        result *= currentOpStack.pop(); 
       } 
       break; 
      case "/": 
       result = currentOpStack.pop(); 
       while(!currentOpStack.isEmpty()){ 
        result /= currentOpStack.pop(); 
       } 
       break; 
      case "+": 
       result = currentOpStack.pop(); 
       while(!currentOpStack.isEmpty()){ 
        result += currentOpStack.pop(); 
       } 
       break; 
      case "-": 
       result = currentOpStack.pop(); 
       while(!currentOpStack.isEmpty()){ 
        result -= currentOpStack.pop(); 
       } 
       break; 

      default: 
       result = currentOpStack.pop(); 
       break; 
     } 

     exprStack.push(result); 

    } 

    /** 
    * This function evaluates current Lisp expression in inputExpr 
    * It return result of the expression 
    * 
    * The algorithm: 
    * 
    * Step 1 Scan the tokens in the string. 
    * Step 2  If you see an operand, push operand object onto the exprStack 
    * Step 3   If you see "(", next token should be an operator 
    * Step 4  If you see an operator, push operator object onto the exprStack 
    * Step 5  If you see ")", do steps 6,7,8 in evaluateCurrentOperation() : 
    * Step 6   Pop operands and push them onto currentOpStack 
    *     until you find an operator 
    * Step 7   Apply the operator to the operands on currentOpStack 
    * Step 8   Push the result into exprStack 
    * Step 9 If you run out of tokens, the value on the top of exprStack is 
    *   is the result of the expression. 
    */ 
    public double evaluate() 
    { 
     // only outline is given... 
     // you need to add statements/local variables 
     // you may delete or modify any statements in this method 

     // use scanner to tokenize inputExpr 
     Scanner inputExprScanner = new Scanner(inputExpr); 

     // Use zero or more white space as delimiter, 
     // which breaks the string into single character tokens 
     inputExprScanner = inputExprScanner.useDelimiter("\\s*"); 

     // Step 1: Scan the tokens in the string. 
     while (inputExprScanner.hasNext()) 
     { 

      // Step 2: If you see an operand, push operand object onto the exprStack 
      if (inputExprScanner.hasNextInt()) 
      { 
       // This force scanner to grab all of the digits 
       // Otherwise, it will just get one char 
       String dataString = inputExprScanner.findInLine("\\d+"); 

     // more ... 
       exprStack.push(Double.parseDouble(dataString)); 
      } 
      else 
      { 
       // Get next token, only one char in string token 
       String aToken = inputExprScanner.next(); 
       char item = aToken.charAt(0); 

       switch (item) 
       { 
       case '(': 
        break; 

       case ')': 
        evaluateCurrentOperation(); 
        break; 

       case'*': 
        exprStack.push("*"); 
        break; 

       case'+': 
        exprStack.push("+"); 
        break; 

       case'/': 
        exprStack.push("/"); 
        break; 

       case'-': 
        exprStack.push("-"); 
        break; 

       // Step 3: If you see "(", next token shoube an operator 
       // Step 4: If you see an operator, push operator object onto the exprStack 
       // Step 5: If you see ")" do steps 6,7,8 in evaluateCurrentOperation() : 
        default: // error 
         throw new SimpleLispExpressionEvaluatorException(item + " is not a legal expression operator"); 
       } // end switch 
      } // end else 
     } // end while 

     // Step 9: If you run out of tokens, the value on the top of exprStack is 
     //   is the result of the expression. 
     // 
     //   return result 
     return Double.parseDouble(String.valueOf(exprStack.pop())); 
    } 


    //===================================================================== 

    // This static method is used by main() only 
    private static void evaluateExprTest(String s, SimpleLispExpressionEvaluator expr) 
    { 
     Double result; 
     System.out.println("Expression " + s); 
    expr.reset(s); 
     result = expr.evaluate(); 
     System.out.printf("Result %.2f\n", result); 
     System.out.println("-----------------------------"); 
    } 

    // define few test cases, exception may happen 
    public static void main (String args[]) 
    { 
     SimpleLispExpressionEvaluator expr= new SimpleLispExpressionEvaluator(); 
     String test1 = "(+ (- 6) (* 2 3 4) (/ (+ 3) (* 1) (- 2 3 1)))"; 
     String test2 = "(+ (- 632) (* 21 3 4) (/ (+ 32) (* 1) (- 21 3 1)))"; 
     String test3 = "(+ (/ 2) (* 2) (/ (+ 1) (+ 1) (- 2 1)))"; 
     String test4 = "(+ (/2))"; 
     String test5 = "(+ (/2 3 0))"; 
     String test6 = "(+ (/ 2) (* 2) (/ (+ 1) (+ 3) (- 2 1))))"; 
     String test7 = "(+ 100)"; 
     String test8 = "(+ 100 5 5 5)"; 
     String test9 = "(*(/100 5)4  10)"; 
     String test10 ="(+ 100)"; 
     String test11 ="(+ (- 6) (* 2 3 4) (/ (+ 3) (* 1) (- 2 3 1)))"; 
     String test12 ="(+ (- 632) (* 21 3 4) (/ (+ 32) (* 1) (- 21 3 1)))"; 
     String test13 =""; 
     String test14 =""; 

    evaluateExprTest(test1, expr); 
    evaluateExprTest(test2, expr); 
    evaluateExprTest(test3, expr); 
    evaluateExprTest(test4, expr); 
    evaluateExprTest(test5, expr); 
    evaluateExprTest(test6, expr); 
    evaluateExprTest(test7, expr); 
    evaluateExprTest(test8, expr); 
    evaluateExprTest(test9, expr); 
    evaluateExprTest(test10, expr); 
    evaluateExprTest(test11, expr); 
    evaluateExprTest(test12, expr); 
    //evaluateExprTest(test13, expr); 
    //evaluateExprTest(test14, expr); 
    } 
} 

當我運行它才能正確測試3,4,5,7,8,9,10工作基礎上：http://joeganley.com/code/jslisp.html

Expression (+ (- 6) (* 2 3 4) (/ (+ 3) (* 1) (- 2 3 1))) 
Result 28.50 
----------------------------- 
Expression (+ (- 632) (* 21 3 4) (/ (+ 32) (* 1) (- 21 3 1))) 
Result 885.88 
----------------------------- 
Expression (+ (/ 2) (* 2) (/ (+ 1) (+ 1) (- 2 1))) 
Result 5.00 
----------------------------- 
Expression (+ (/2)) 
Result 2.00 
----------------------------- 
Expression (+ (/2 3 0)) 
Result Infinity 
----------------------------- 
Expression (+ 100) 
Result 100.00 
----------------------------- 
Expression (+ 100 5 5 5) 
Result 115.00 
----------------------------- 
Expression (*(/100 5)4  10) 
Result 800.00 
----------------------------- 
Expression (+ 100) 
Result 100.00 
----------------------------- 
Expression (+ (- 6) (* 2 3 4) (/ (+ 3) (* 1) (- 2 3 1))) 
Result 28.50 
----------------------------- 
Expression (+ (- 632) (* 21 3 4) (/ (+ 32) (* 1) (- 21 3 1))) 
Result 885.88 
----------------------------- 

這些結果，只有當我刪除發生測試6，因爲它會發出異常並停止執行。任何想法我錯了什麼地方？

錯誤，如果6註釋掉了：

Exception in thread "main" java.util.EmptyStackException 
    at java.util.Stack.peek(Unknown Source) 
    at java.util.Stack.pop(Unknown Source) 
    at PJ2.SimpleLispExpressionEvaluator.evaluateCurrentOperation(SimpleLispExpressionEvaluator.java:143) 
    at PJ2.SimpleLispExpressionEvaluator.evaluate(SimpleLispExpressionEvaluator.java:248) 
    at PJ2.SimpleLispExpressionEvaluator.evaluateExprTest(SimpleLispExpressionEvaluator.java:292) 
    at PJ2.SimpleLispExpressionEvaluator.main(SimpleLispExpressionEvaluator.java:321) 

Answer 1

這不是一個真正的Lisp。這只是前綴形式的算術表達式。約有0.1％的Lisp。 Lisp有點多：函數，符號，缺陷單元，列表操作，...

您的測試表達式6在最後有一個額外的括號。

通常，您應該開發自己的代碼，以便可以輕鬆檢測到語法錯誤。這意味着錯誤檢測，錯誤處理和錯誤報告。一個典型的Lisp系統（比如SBCL，CLISP，...）會以簡單的英文向用戶報告額外的括號。