Bookmark You are to write a program name expressionTree.java that evaluates an i

Question

Bookmark

You are to write a program name expressionTree.java that evaluates an infix expression entered by the user. The expression may contain the following tokens:
(1) Integer constants (a series of decimal digits).
(2)   One alphabetic character - "x" (representing a value to be supplied later).
(3)   Binary operators (+, -, *, / and % (modulo)).
(4)   Parentheses
        
You will parse the input expression creating an expression tree with the tokens, then use the postOrder tree traversal algorithm to extract a postfix expression from the tree. Display this postfix expression(String).You will supply this postfix expression (string) to the calculator engine (a function that you will write) to produce a result.

Spaces between tokens are allowed but not required. The program will repeatedly prompt the user for the value of x, displaying the value of the expression each time. When the user enters the letter q instead of a number, the program terminates.

The following example illustrates the behavior of the program (user input is in bold):

Enter infix expression: (x + 1) * (x – 2) / 4
Converted expression: x 1 + x 2 - * 4 /

Enter value of x: 5
Answer to expression: 4

Enter value of x: 7
Answer to expression: 10

Enter value of x: q

If the infix expression contains an error of any kind, the program must display the message Error in expression (with an optional explanation) and then terminate. The following examples illustrate various types of errors:

Enter infix expression: 1 2 +
Error in expression!! No operator between operands. Also last token must be an operand.

Enter infix expression: 10.4
Error in expression!! Cannot accept floating point numbers.

Enter infix expression: 1 ( + 2)
Error in expression!! No operator between operand and left parentheses.

Enter infix expression: 5 – (x – 2))
Error in expression!! No matching left parentheses for a right parentheses.

Enter infix expression: 1 ** 2
Error in expression!! The * operator cannot be preceded by a * operator.

The output of your program must match the format illustrated in this example.

Here are some other additional requirements for this program:

(1)   You must use stack objects and list during the translation from infix to the parse tree and during the evaluation of the postfix expression.

(2)   Operators must have the correct precedence and associativity.

Explanation / Answer

*****************************************expressionTree.java*****************************

package expressiontree;

import java.io.IOException;
import java.util.Scanner;
import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;

public class expressionTree {
private Stack theStack;
private String input;
private String output = "";
public expressionTree(String s1) {
input = s1;
int stackSize = input.length();
theStack = new Stack(stackSize);
}
public String performTrans() {
for (int j = 0; j < input.length(); j++) {
char ch = input.charAt(j);
switch (ch) {
case '+':
case '-':
isOperator(ch, 1);
break;
case '*':
case '/':
isOperator(ch, 2);
break;
case '(':
theStack.push(ch);
break;
case ')':
isParen(ch);
break;
default:
output = output + ch;
break;
}
}
while (!theStack.isEmpty()) {
output = output + theStack.pop();
}
System.out.println(output);
return output;
}
public void isOperator(char opThis, int prec1) {
while (!theStack.isEmpty()) {
char opTop = theStack.pop();
if (opTop == '(') {
theStack.push(opTop);
break;
}
else {
int prec2;
if (opTop == '+' || opTop == '-')
prec2 = 1;
else
prec2 = 2;
if (prec2 < prec1) {
theStack.push(opTop);
break;
}
       else
output = output + opTop;
}
}
theStack.push(opThis);
}
public void isParen(char ch){
while (!theStack.isEmpty()) {
char chx = theStack.pop();
if (chx == '(')
break;
else
output = output + chx;
}
}
public static void main(String[] args) throws IOException {
Scanner scn=new Scanner(System.in);
int x1 = 0;
String temp;
System.out.println("Please enter the expression:");
String input = scn.next();
String output,replacer;
char[] arr=new char[input.length()];
expressionTree e1 = new expressionTree(input);
output = e1.performTrans();
System.out.println("Postfix is " + output + ' ');
do{
System.out.println("Please enter the value of X:");
temp=scn.next();
if(temp!="q"){
replacer=input.replace("x",temp );
//to evaluate the string in arithematic following function is defined
ScriptEngine engine = new ScriptEngineManager().getEngineByExtension("js");
try {
// Evaluate the expression
Object result = engine.eval(replacer);
System.out.println(" Answer to the expression is:" + result);
}
catch (ScriptException e) {
// Something went wrong
e.printStackTrace();
}


}
else
break;
}while(temp!="q");
  
}
}

***************************Stack.Java*****************************************

package expressiontree;
class Stack {
private int mSize;
private char[] arrStack;
private int top;
public Stack(int max) {
mSize = max;
arrStack = new char[mSize];
top = -1;
}
public void push(char j) {
arrStack[++top] = j;
}
public char pop() {
return arrStack[top--];
}
public char peek() {
return arrStack[top];
}
public boolean isEmpty() {
return (top == -1);
}
}

*********************output**********************************************

Please enter the expression:
(x+1)*(x-2)/4
x1+x2-*4/
Postfix is x1+x2-*4/

Please enter the value of X:

5
Answer to the expression is:4
Please enter the value of X:
7
Answer to the expression is:10

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.