fork download
copy 
  1. import java.util.*;
  2.  
  3. class LispEvaluator {
  4.  
  5. /**
  6.  * Input expression
  7.  */
  8. private String inputExp;
  9.  
  10. /**
  11.  * Stacks created for the main expression and current operation.
  12.  */
  13. private Stack<Object> expStack;
  14. private Stack<Double> currentOpStack;
  15.  
  16.  
  17. /**
  18.  * Default constructor initializes input and creates Stack objects.
  19.  */
  20. public LispEvaluator()
  21. {
  22.     inputExp = "";
  23.     expStack = new Stack<Object>();
  24.     currentOpStack = new Stack<Double>();
  25. }
  26.  
  27. /**
  28.  * Constructor sets inputExpr to inputExpression and creates Stack objects.
  29.  * @param inputExpression
  30.  * @throws LispEvaluatorException
  31.  */
  32. public LispEvaluator(String input_Expression) throws LispEvaluatorException 
  33. {
  34.     // If there is no expression, throws an exception.
  35.     if(input_Expression == null)
  36.     {
  37.         throw new LispEvaluatorException("Input statement is null.");
  38.     }
  39.  
  40.     // Objects created
  41.     inputExp = input_Expression;
  42.     expStack = new Stack<Object>();
  43.     currentOpStack = new Stack<Double>();
  44. }
  45.  
  46. /**
  47.  * evaluateCurrentOperation() method evaluates the current operation:
  48.  * - Pops operands from expStack and pushes them onto currentOpStack until it finds an operator.
  49.  * - Uses the operator on the operands on currentOpStack.
  50.  * - Pushes the result into exprStack.
  51.  */
  52. private void evaluateCurrentOperation()
  53. {
  54.     String current_Operation;
  55.     boolean numeric = true;
  56.  
  57.     // Do... while statement sets current operation (while it is numeric).
  58.     do{
  59.         current_Operation = (String.valueOf(expStack.pop()));
  60.  
  61.         try{
  62.             Double number = Double.parseDouble(current_Operation);
  63.             currentOpStack.push(number);
  64.  
  65.         }catch(NumberFormatException nfe){
  66.             numeric = false;
  67.         }
  68.     } while(numeric);
  69.  
  70.  
  71.     double result;
  72.     switch (current_Operation) {
  73.         case "*":
  74.         	if (currentOpStack.isEmpty()) {
  75.         		result = 1;
  76.         		break;
  77.         	}
  78.             result = currentOpStack.pop();
  79.             while(!currentOpStack.isEmpty()){
  80.                 result *= currentOpStack.pop();
  81.             }
  82.             break;
  83.         case "/":
  84.             result = currentOpStack.pop();
  85.             while(!currentOpStack.isEmpty()){
  86.                 result /= currentOpStack.pop();
  87.             }
  88.             break;
  89.         case "+":
  90.             result = currentOpStack.pop();
  91.             while(!currentOpStack.isEmpty()){
  92.                 result += currentOpStack.pop();
  93.             }
  94.             break;
  95.         case "-":
  96.             result = currentOpStack.pop();
  97.             if (currentOpStack.isEmpty()) {
  98.             	// Unary minus
  99.             	result = -result;
  100.             	break;
  101.             }
  102.             while(!currentOpStack.isEmpty()){
  103.                 result -= currentOpStack.pop();
  104.             }
  105.  
  106.             break;
  107.  
  108.         default:
  109.             result = currentOpStack.pop();
  110.             break;
  111.     }
  112.  
  113.     expStack.push(result);
  114.  
  115. }
  116.  
  117. /**
  118.  * evaluate() method evaluates the current Lisp expression in inputExpr and returns the result.
  119.  * @throws LispEvaluatorException 
  120.  */
  121. public double evaluate() throws LispEvaluatorException
  122. {
  123.     Scanner inputExprScanner = new Scanner(inputExp);
  124.  
  125.     /**
  126.      * Breaks the string into single characters using a delimiter.
  127.      */
  128.     inputExprScanner = inputExprScanner.useDelimiter("\\s*");
  129.  
  130.     /**
  131.      * Scans the tokens in the string (runs while there is a next token).
  132.      */
  133.     while (inputExprScanner.hasNext())
  134.     {
  135.  
  136.         /**
  137.          * If it has an operand, pushes operand object onto the exprStack.
  138.          */
  139.         if (inputExprScanner.hasNextInt())
  140.         {
  141.             /**
  142.              * Scanner gets all of the digits (regular expression \\d+ means any digit).
  143.              */
  144.             String dataString = inputExprScanner.findInLine("\\d+");
  145.  
  146.             expStack.push(Double.parseDouble(dataString));
  147.         }
  148.  
  149.         else
  150.         {
  151.             /**
  152.              * Gets one character in String token.
  153.              */
  154.             String token = inputExprScanner.next();
  155.             char item = token.charAt(0);
  156.  
  157.             switch(item)
  158.             {
  159.             // If "(", next token is an operator (so do nothing).
  160.             case '(':
  161.                 break;
  162.  
  163.             // If ")", it will evaluate that expression since parenthesis are closed.
  164.             case ')':                   
  165.                 evaluateCurrentOperation();
  166.  
  167.                 break; 
  168.  
  169.             // If there is an operator "* + / -", then it pushes the operator onto exprStack.
  170.             case'*':
  171.                 expStack.push("*");
  172.                 break;
  173.  
  174.             case'+':
  175.                 expStack.push("+");
  176.                 break; 
  177.  
  178.             case'/':
  179.                 expStack.push("/");
  180.                 break;
  181.  
  182.             case'-':
  183.                 expStack.push("-");
  184.                 break;  
  185.  
  186.             /**
  187.              * Default throws an error.
  188.              */
  189.                 default:
  190.                     throw new LispEvaluatorException(item + " is not a valid operator");
  191.             } // end switch
  192.         } // end else
  193.     } // end while
  194.  
  195.     /**
  196.      * If you run out of tokens, the value on the top of exprStack is the result of the expression.
  197.      * 
  198.      */
  199.  
  200.     return Double.parseDouble(String.valueOf(expStack.pop()));
  201. }
  202.  
  203. /**
  204.  * Reset method sets inputExpr to inputExpression and clears Stack objects.
  205.  * @param inputExpression
  206.  * @throws LispEvaluatorException
  207.  */
  208. public void reset(String inputExpression) throws LispEvaluatorException 
  209. {
  210.     if(inputExpression == null)
  211.     {
  212.         throw new LispEvaluatorException("Input statement is null");
  213.     }
  214.  
  215.     inputExp = inputExpression;
  216.     expStack.clear();
  217.     currentOpStack.clear();
  218. }
  219.  
  220. /**
  221.  * Test method to print the result of the expression evaluator.
  222.  * @param s
  223.  * @param expr
  224.  * @throws LispEvaluatorException
  225.  */
  226. private static void evaluateExprTest(String s, LispEvaluator expr) throws LispEvaluatorException
  227. {
  228.     Double result;
  229.     System.out.println("Expression: " + s);
  230. expr.reset(s);
  231.     result = expr.evaluate();
  232.     System.out.printf("Result: %.2f\n", result);
  233.     System.out.println("-------");
  234. }
  235.  
  236. /**
  237.  * Main method uses test cases to test the evaluator.
  238.  * @param args
  239.  * @throws LispEvaluatorException
  240.  */
  241. public static void main (String args[]) throws LispEvaluatorException
  242. {
  243.     LispEvaluator expr= new LispEvaluator();
  244.  
  245.     /**
  246.      * Expressions are tested.
  247.      * Note: For each operation written as (- 6), in order for the Stack to continue,
  248.      * it needs to be written as (- 0 6). This way, it is subtracting from a digit.
  249.      */
  250.     //String test1 = "(+ 5 0 10)";
  251.     //String test2 = "(+ 5 0 10 (- 7 2))";
  252.     String test3 = "(+ (- 6) (* 2 3 4) (/ (+ 3) (*) (- 2 3 1)))";
  253.     //String test4 = "(+ (- 0 632) (* 21 3 4) (/ (+ 32) (* 1) (- 21 3 1)))";
  254.     //String test5 = "(+ 2 6) (* 12 18) (/ (+ 32) (* 1) (- 21 3 1))";
  255.     //String test6 = "(+ 1 2 (- 5 1) (*4 11 14))";
  256.  
  257.     //evaluateExprTest(test1, expr);
  258.     //evaluateExprTest(test2, expr);
  259.     evaluateExprTest(test3, expr);
  260.     //evaluateExprTest(test4, expr);
  261.     //evaluateExprTest(test5, expr);
  262.     //evaluateExprTest(test6, expr);
  263.  
  264. }
  265.  
  266. public static class LispEvaluatorException extends Exception{
  267.  
  268.     public LispEvaluatorException(String message) {
  269.         super(message);
  270.  
  271.     }
  272. }
  273.  
  274. }
  275.  
Success #stdin #stdout 0.06s 711680KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Expression: (+ (- 6) (* 2 3 4) (/ (+ 3) (*) (- 2 3 1)))
Result: 16.50
-------
https://ideone.com/9uuT7Q
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!