In the language Lisp, each of the four basic arithmetic operators appears before
ID: 3532836 • Letter: I
Question
In the language Lisp, 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 Design and implement an algorithm that uses a stack to evaluate a legal Lisp expression composed of the four basic operators and integer values. Write a program that reads such expressions and demonstrates your algorithm.Explanation / Answer
Here you go :
import java.util.Stack;
public class SmallLisp {
Stack<String> stack;
public SmallLisp(){
String[] tokens = new String[]{"(","/","2","3","2",")"};
stack = new Stack<String>();
for (int i=0;i<tokens.length;i++){
stack.push(tokens[i]);
if(tokens[i].equals(")")) Interprete();
}
}
public void Interprete(){
String tok;
Stack<String> callStack = new Stack<String>();
tok = stack.pop(); /* This is the ) character */
while(!(tok=stack.pop()).equals("(")){
callStack.push(tok);
}
Call(callStack);
}
public void Call(Stack<String> callStack){
String func = callStack.pop(); /* This is the operator or function */
if(func.equals("+"))
{
double result = Plus(callStack);
stack.push(String.valueOf(result));
System.out.println("Sum : "+result);
}
else if(func.equals("-"))
{
double result=Double.parseDouble(callStack.pop())- Minus(callStack);
stack.push(String.valueOf(result));
System.out.println("Subract : "+result);
}
else if(func.equals("*"))
{
double result=Multiply(callStack);
stack.push(String.valueOf(result));
System.out.println("Multiply : "+result);
}
else if(func.equals("/"))
{
double result=Double.parseDouble(callStack.pop())/Multiply(callStack);
stack.push(String.valueOf(result));
System.out.println("Divide : "+result);
}
}
public double Plus(Stack<String> callStack){
double a = Double.parseDouble(callStack.pop());
double b = Double.parseDouble(callStack.pop());
return(a+b);
}
public double Minus(Stack<String> callStack){
double a = Double.parseDouble(callStack.pop());
double b = Double.parseDouble(callStack.pop());
return(-a-b);
}
public double Multiply(Stack<String> callStack){
double a = Double.parseDouble(callStack.pop());
double b = Double.parseDouble(callStack.pop());
return(a*b);
}
public double Divide(Stack<String> callStack){
double a = Double.parseDouble(callStack.pop());
double b = Double.parseDouble(callStack.pop());
return(a/b);
}
public static void main(String[] args) {
new SmallLisp();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.