Java LISP implementation almost working -
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 "" // create stack objects public simplelispexpressionevaluator() { // add statements inputexpr = ""; exprstack = new stack<object>(); currentopstack = new stack<double>(); } // default constructor // set inputexpr 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 inputexpression // clear stack objects public void reset(string inputexpression) { // add statements if(inputexpression == null) { throw new simplelispexpressionevaluatorexception(); } inputexpr = inputexpression; exprstack.clear(); currentopstack.clear(); } // function evaluate current operator operands // see complete algorithm in evaluate() // // main steps: // pop operands exprstack , push them onto // currentopstack until find operator // apply operator operands on currentopstack // push result 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); } /** * function evaluates current lisp expression in inputexpr * return result of expression * * algorithm: * * step 1 scan tokens in string. * step 2 if see operand, push operand object onto exprstack * step 3 if see "(", next token should operator * step 4 if see operator, push operator object onto exprstack * step 5 if see ")", steps 6,7,8 in evaluatecurrentoperation() : * step 6 pop operands , push them onto currentopstack * until find operator * step 7 apply operator operands on currentopstack * step 8 push result exprstack * step 9 if run out of tokens, value on top of exprstack * result of expression. */ public double evaluate() { // outline given... // need add statements/local variables // may delete or modify statements in method // use scanner tokenize inputexpr scanner inputexprscanner = new scanner(inputexpr); // use 0 or more white space delimiter, // breaks string single character tokens inputexprscanner = inputexprscanner.usedelimiter("\\s*"); // step 1: scan tokens in string. while (inputexprscanner.hasnext()) { // step 2: if see operand, push operand object onto exprstack if (inputexprscanner.hasnextint()) { // force scanner grab of digits // otherwise, 1 char string datastring = inputexprscanner.findinline("\\d+"); // more ... exprstack.push(double.parsedouble(datastring)); } else { // next token, 1 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 see "(", next token shoube operator // step 4: if see operator, push operator object onto exprstack // step 5: if see ")" steps 6,7,8 in evaluatecurrentoperation() : default: // error throw new simplelispexpressionevaluatorexception(item + " not legal expression operator"); } // end switch } // end else } // end while // step 9: if run out of tokens, value on top of exprstack // result of expression. // // return result return double.parsedouble(string.valueof(exprstack.pop())); } //===================================================================== // static method used main() 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); } } when run tests 3,4,5,7,8,9,10 work correctly based on: 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 ----------------------------- these results occur when remove test 6 because gives exception , stops executing. idea on i've gone wrong?
error if 6 uncommented out:
exception in thread "main" java.util.emptystackexception @ java.util.stack.peek(unknown source) @ java.util.stack.pop(unknown source) @ pj2.simplelispexpressionevaluator.evaluatecurrentoperation(simplelispexpressionevaluator.java:143) @ pj2.simplelispexpressionevaluator.evaluate(simplelispexpressionevaluator.java:248) @ pj2.simplelispexpressionevaluator.evaluateexprtest(simplelispexpressionevaluator.java:292) @ pj2.simplelispexpressionevaluator.main(simplelispexpressionevaluator.java:321)
that's not lisp. that's arithmetic expressions in prefix form. 0.1% of lisp. lisp bit more: functions, symbols, cons cells, list operations, ...
your test expression 6 has parenthesis @ end.
generally should develop code syntax errors can detected. means error detection, error handling , error reporting. typical lisp system (say, sbcl, clisp, ...) report parenthesis user in plain english.
Comments
Post a Comment