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 %.2fn", 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
-----------------------------
这些结果只在我删除test 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)
这不是真正的Lisp。这就是前缀形式的算术表达式。Lisp的0.1%。Lisp则更多:函数、符号、cons单元格、列表操作……
您的测试表达式6在末尾有一个额外的括号。
一般来说，你应该开发你的代码，使语法错误可以很容易地检测到。这意味着错误检测、错误处理和错误报告。一个典型的Lisp系统(比如，SBCL, clp，…)会用简单的英语向用户报告这个额外的括号。