Question

Lisp

In the language Lisp1 , each of the four basic arithmetic operators appears before an arbitrary number of operands, which are separated by spaces. The resulting expression is enclosed in parentheses. The operators behave as follows:

(+ a b c ...) returns the sum of all the operands, and (+) returns 0.

(- a b c ...) returns a - b - c - ..., and (- a) returns -a. The minus operator must have at least one operand.

(* a b c ...) returns the product of all the operands, and (*) returns 1.

(/ a b c ...) returns a / b / c /..., and (/ a) returns 1 / a. The divide operator must have at least one operand.

You can form larger arithmetic expressions by combining these basic expressions using a fully parenthesized prefix notation. For example, the following is a valid Lisp expression:

(+ (- 6) (* 2 3 4) (/ (+ 3) (*) (- 2 3 1)))

This expression is evaluated successively as follows:

(+ (- 6) (* 2 3 4) (/ 3 1 -2))

(+ -6 24 -1.5)

16.5

Write a program that reads such expressions and demonstrates your algorithm. We have provided you some starter code, and you are asked to complete the rest.

LISPTOKEN

package hw5;

public class LispToken

{

private Character operator;

private Double operand;

private boolean isOperator;

/** Constructors for objects of class LispToken. */

public LispToken(Character anOperator)

{

operator = anOperator;

isOperator = true;

operand = 0.0;

}

public LispToken(Double value)

{

operand = value;

isOperator = false;

operator = ' ';

}

/** TODO: Applies this operator to two given operand values.

@param value1 The value of the first operand.

@param value2 The value of the second operand.

@return The real result of the operation.

TODO: You need to complete this method.

*/

public Double applyOperator(Double value1, Double value2)

{

}

/** Gets the identity value of this operator.

For example, x + 0 = x, so 0 is the identity for +

and will be the value associated with the expression (+).

@return The identity value of the operator. */

public Double getIdentity()

{

Double result = 0.0;

switch (operator)

{

case '+':

result = 0.0;

break;

case '-':

result = 0.0;

break;

case '*':

result = 1.0;

break;

case '/':

result = 1.0;

break;

}

return result;

}

/** Detects whether this operator returns a value when it has no operands.

@return True if the operator returns a value when it has no operands,

or false if not. */

public boolean takesZeroOperands()

{

boolean result = false;

switch (operator)

{

case '+':

result = true;

break;

case '-':

result = false;

break;

case '*':

result = true;

break;

case '/':

result = false;

break;

}

return result;

}

/** Gets the value of this operand.

@return The real value of the operand. */

public Double getValue()

{

return operand;

}

/** Returns true if the object is an operator.

@return True is this object is an operator. */

public boolean isOperator()

{

return isOperator;

}

public String toString()

{

String result = null;

if (isOperator)

result = operator.toString();

else

result = operand.toString();

return result;

}

}

LISPQUESTION

package hw5;

import java.util.Scanner;

import java.util.Stack;

public class LispQuestion

{

/** Evaluates a Lisp expression.

The algorithm:

Scan the tokens in the string.

If you see "(", push the next operator onto the stack.

If you see an operand, push it onto the stack.

If you see ")",

Pop operands and push them onto a second stack

until you find an operator.

Apply the operator to the operands on the second stack.

Push the result on the stack.

If you run out of tokens, the value on the top of the stack is

the value of the expression.

@param lispExp A string that is a valid lisp expression.

@return A double that is the value of the expression.

@TODO: You need to complete this method. This method must call the applyOperator from LispToken class.

*/

public static double evaluate(String lispExp)

{

}

public static void main (String args[])

{

Double result;

String test1 = "(+ (- 6) (* 2 3 4) (/ (+ 3) (*) (- 2 3 1)))";

result = evaluate(test1);

System.out.println("Expression " + test1 + " evaluates to " + result);

String test2 = "(+ (- 632) (* 21 3 4) (/ (+ 32) (*) (- 21 3 1)))";

result = evaluate(test2);

System.out.println("Expression " + test2 + " evaluates to " + result);

String test3 = "(+ (/ 2) (* 2) (/ (+ 1) (+) (- 2 1 )))";

result = evaluate(test3);

System.out.println("Expression " + test3 + " evaluates to " + result);

}

}

/*

Expression (+ (- 6) (* 2 3 4) (/ (+ 3) (*) (- 2 3 1))) evaluates to 16.5

Expression (+ (- 632) (* 21 3 4) (/ (+ 32) (*) (- 21 3 1))) evaluates to -378.11764705882354

Expression (+ (/ 2) (* 2) (/ (+ 1) (+) (- 2 1 ))) evaluates to Infinity

*/

Answer 1

LispToken.java

==================================

package hw5;

public class LispToken {
   private Character operator;
   private Double operand;
   private boolean isOperator;
  
   /** Constructors for objects of class LispToken. */
   public LispToken(Character anOperator) {
       operator = anOperator;
       isOperator = true;
       operand = 0.0;
   }
   public LispToken(Double value) {
       operand = value;
       isOperator = false;
       operator = ' ';
   }
  
   /** Applies this operator to two given operand values.
   @param value1 The value of the first operand.
   @param value2 The value of the second operand.
   @return The real result of the operation.
   */
   public Double applyOperator(Double value1, Double value2) {
       // check for operator
       if(operator == '+') {
           return value1 + value2;
       }
       else if(operator == '-') {
           return value1 - value2;
       }
       else if(operator == '*') {
           return value1*value2;
       }
       else if(operator == '/') {
           return value1 / value2;
       }
       else {
           // throw exception if operator is not valid
           throw new IllegalArgumentException();
       }
   }
      
   /** Gets the identity value of this operator.
   For example, x + 0 = x, so 0 is the identity for +
   and will be the value associated with the expression (+).
   @return The identity value of the operator. */
   public Double getIdentity()   {
       Double result = 0.0;
       switch (operator) {
           case '+':
               result = 0.0;
               break;
           case '-':
               result = 0.0;
               break;
           case '*':
               result = 1.0;
               break;
           case '/':
               result = 1.0;
               break;
       }
       return result;
   }
      
   /** Detects whether this operator returns a value when it has no operands.
   @return True if the operator returns a value when it has no operands,
   or false if not. */
   public boolean takesZeroOperands() {
       boolean result = false;
       switch (operator) {
           case '+':
               result = true;
               break;
           case '-':
               result = false;
               break;
           case '*':
               result = true;
               break;
           case '/':
               result = false;
               break;
       }
       return result;
   }
  
   /** Gets the value of this operand.
   @return The real value of the operand. */
   public Double getValue() {
       return operand;
   }

   /** Returns true if the object is an operator.
   @return True is this object is an operator. */
   public boolean isOperator()   {
       return isOperator;
   }
  
   public String toString() {
       String result = null;
       if (isOperator)
           result = operator.toString();
       else
           result = operand.toString();
       return result;
   }
}

====================================

LispQuestion.java

====================================

package hw5;

import java.util.Stack;

public class LispQuestion {
  
   /** Evaluates a Lisp expression.
   The algorithm:
   Scan the tokens in the string.
   If you see "(", push the next operator onto the stack.
   If you see an operand, push it onto the stack.
   If you see ")",
   Pop operands and push them onto a second stack
   until you find an operator.
   Apply the operator to the operands on the second stack.
   Push the result on the stack.
   If you run out of tokens, the value on the top of the stack is
   the value of the expression.
   @param lispExp A string that is a valid lisp expression.
   @return A double that is the value of the expression.
   @TODO: You need to complete this method. This method must call the applyOperator from LispToken class.
   */
   public static double evaluate(String lispExp) {
       // create a stack to hold data
       Stack<LispToken> operators = new Stack<LispToken>();
       Stack<Stack<Double>> stack = new Stack<Stack<Double>>();
       Stack<Double> operands = new Stack<Double>();
       boolean isNextOperator = false;
       String digits = "";
       // read each character from lispExp
       char c = 0;
       for(int i=0;i<lispExp.length();i++) {
           c = lispExp.charAt(i);
           // ignore white space
           if(c == ' ') {
               // parse digits of string to double
               if(digits.length()>0) {
                   double number = Double.parseDouble(digits);
                   // add number to operands
                   operands.add(number);
               }
               // reset digits
               digits = "";
           }
           else {
               // check for open parenthesis
               if(c == '(') {
                   // set flag to true as next char is operator
                   isNextOperator = true;
                   // check operator size
                   if(operators.size()>0) {
                       // put operands to stack
                       stack.add(operands);
                       operands = new Stack<Double>();
                   }
               }
               else if(c == ')') {
                   // parse digits of string to double
                   if(digits.length()>0) {
                       double number = Double.parseDouble(digits);
                       // add number to operands
                       operands.add(number);
                   }
                   // reset digits
                   digits = "";
                   // check for close parenthesis
                   // get the operator
                   LispToken operator = operators.pop();
                   double value = 0.0;
                   // check for operand size
                   if(operands.size()==0) {
                       // check if operator takes zero operand
                       if(operator.takesZeroOperands()) {
                           value = operator.getIdentity();
                       }
                       else {
                           // invalid expression
                           // throw exception
                           throw new IllegalArgumentException();
                       }
                   }
                   else if(operands.size() == 1) {
                       // calculate value for one operand
                       value = operator.applyOperator(operator.getIdentity(), operands.pop());  
                   }
                   else {
                       // apply operator to each operand in stack
                       int size = operands.size();
                       value = operands.elementAt(0);
                       for(int j=1;j<size;j++) {
                           double operand = operands.elementAt(j);
                           value = operator.applyOperator(value, operand);
                       }
                       operands.clear();
                   }
                   // set new operands
                   if(operators.size()>0) {
                       operands = stack.pop();
                   }
                   // add value to new operands
                   operands.add(value);
               }
               else {
                   // check if current char is operator
                   if(isNextOperator) {
                       // push operator to stack
                       operators.add(new LispToken(c));
                       // set flag to false
                       isNextOperator = false;
                   }
                   else {
                       // push operand to stack
                       digits = digits + c;
                   }
               }
           }
       }
       return operands.pop();
   }
  
   public static void main (String args[]) {
       Double result;
       String test1 = "(+ (- 6) (* 2 3 4) (/ (+ 3) (*) (- 2 3 1)))";
       result = evaluate(test1);
       System.out.println("Expression " + test1 + " evaluates to " + result);
       String test2 = "(+ (- 632) (* 21 3 4) (/ (+ 32) (*) (- 21 3 1)))";
       result = evaluate(test2);
       System.out.println("Expression " + test2 + " evaluates to " + result);
       String test3 = "(+ (/ 2) (* 2) (/ (+ 1) (+) (- 2 1 )))";
       result = evaluate(test3);
       System.out.println("Expression " + test3 + " evaluates to " + result);
   }
}

/*
Expression (+ (- 6) (* 2 3 4) (/ (+ 3) (*) (- 2 3 1))) evaluates to 16.5
Expression (+ (- 632) (* 21 3 4) (/ (+ 32) (*) (- 21 3 1))) evaluates to -378.11764705882354
Expression (+ (/ 2) (* 2) (/ (+ 1) (+) (- 2 1 ))) evaluates to Infinity
*/

let me know if you have any doubts or problem.