If someone could explain how to do this problem it would be great, thanks. In th
ID: 3737369 • Letter: I
Question
If someone could explain how to do this problem it would be great, thanks.
In the previous assignment, you wrote a Java program that prompted the user for an infix expression and converted the result to postfix, displaying the result in the console window In this assignment, instead of simply displaying the postfix, you will implement a simple interpreter that evaluates the expression, and returns an ordered sequence on one and two operand expressions that can subsequently be evaluated by a simple processor. The point of this assignment is to understand the Stack Interpreter outlined in the Appendix of Assignment 3 Consider the following example: atc*y-d*ix The corresponding Postfix expression is: acy*+dx*- Following the convention of Assignment 3, the expression would be evaluated as follows: Token Stack a c a c y ult of an operation which is subsequently placed back on The indicate the res the stack for further evaluation until all operators have been processed. Your program should list these operations as follows: Infix to Postfix Interpreter Enter expression (blank line to exit): atc y-d*x Evall: Eval4:Explanation / Answer
import acm.program.ConsoleProgram;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class JCalcS extends ConsoleProgram {
private final String SENTINAL = "";
public void run () {
while(true) {
// get user input
String in = readLine(" Enter expression (blank line to exit): ");
if(in.equals(SENTINAL)) break;
StringTokenizer st = new StringTokenizer(in,"+-*/()^",true); // new string tokenizer
Queue inQ = new Queue(); // Stores tokenized input
Queue outQ = new Queue(); // Stores postfix output
Stack opS = new Stack(); // Stores operators during postfix conversion
// Separate elements of input string by tokens (+-*/) and then put everything in a queue
while(st.hasMoreTokens()) {
inQ.enqueue(st.nextToken()); // add next token to the input queue
}
while(inQ.getFront() != null) {
if( !inQ.getFront().data.equals("*")
&& !inQ.getFront().data.equals("/")
&& !inQ.getFront().data.equals("+")
&& !inQ.getFront().data.equals("-")
&& !inQ.getFront().data.equals("(")
&& !inQ.getFront().data.equals(")")
&& !inQ.getFront().data.equals("^")) {
// add directly to output Queue
outQ.enqueue(inQ.dequeue());
} else if (inQ.getFront().data.equals("*")
|| inQ.getFront().data.equals("/")
|| inQ.getFront().data.equals("+")
|| inQ.getFront().data.equals("-")
|| inQ.getFront().data.equals("^")) {
// while (operator at top of stack has higher precedence OR equal precedence
// and is left associative) AND (is not a left bracket)
if (opS.getTop() != null) {
while ( !opS.getTop().data.equals("(") &&
(
( precedenceLevel(opS.getTop().data) > precedenceLevel(inQ.getFront().data) )
|| (
precedenceLevel(opS.getTop().data) == precedenceLevel(inQ.getFront().data)
// only right associative operator we might be using is ^
&& !inQ.getFront().data.equals("^")
)
) ) {
if (opS.getTop().data.equals("(")) break;
// pop operators from the stack
outQ.enqueue(opS.pop());
if(opS.getTop() == null) {
break;
}
}
}
// push read operator to the operator stack
opS.push(inQ.dequeue());
// Next is bracket stuff ()
} else if ( inQ.getFront().data.equals("(") ) {
opS.push(inQ.dequeue());
// if right bracket: pop operators from stack until left bracket is found
} else if ( inQ.getFront().data.equals(")") ) {
inQ.dequeue();
// while top of operator stack is not a left bracket: pop operators to output Queue
while ( !opS.getTop().data.equals("(") ) {
outQ.enqueue(opS.pop());
// if stack runs out without finding a left bracket, there are mismatched brackets
if (opS.getTop() == null) {
// handle error
break;
}
}
// then pop left bracket from operator stack
opS.pop();
}
// once input queue is empty, add remaining operators from stack to output queue
if (inQ.getFront() == null) {
while (opS.getTop() != null) {
outQ.enqueue(opS.pop());
}
}
} // end of shunting yard alogrithm loop
/* beginning of post fix expression evaluation algorithm */
Stack evalS = new Stack(); // Stack for holding operators during evaluation
int evalcounter = 0; // counter for printing output
// loop until output queue is empty
while (outQ.getFront()!=null) {
// if next element is a operator (ie: not an operand)
if(!outQ.getFront().data.equals("+")
&& !outQ.getFront().data.equals("-")
&& !outQ.getFront().data.equals("*")
&& !outQ.getFront().data.equals("/")
&& !outQ.getFront().data.equals("^")
&& !outQ.getFront().data.equals("(")
&& !outQ.getFront().data.equals(")") ) {
// push directly to eval stack
evalS.push(outQ.dequeue());
// else if next element is an operand, evaluate last two operators pushed to stack with
// operand and then push result to stack
} else if (outQ.getFront().data.equals("+")
|| outQ.getFront().data.equals("-")
|| outQ.getFront().data.equals("*")
|| outQ.getFront().data.equals("/")
|| outQ.getFront().data.equals("^")) {
String operator2 = evalS.pop();
String operator1 = evalS.pop();
String operand = outQ.dequeue();
String Eval = "<" + operator1 + operand + operator2 + ">";
evalcounter++;
evalS.push("Eval" + evalcounter);
println("Eval" + evalcounter + ":" + Eval);
}
}
}// end of while loop to loop program
System.exit(0);
}
//Returns the precedence level of passed operator
int precedenceLevel (String operator) {
switch (operator) {
case "+":
case "-":
return 0;
case "*":
case "/":
return 1;
case "^":
return 2;
default:
// if precedenceLevel is called with invalid operator: throw exception
throw new IllegalArgumentException("Invalid operator: " + operator);
}
}
}
----------------------------------------------------------------------------------------------------
public class Queue {
private listNode front;
private listNode rear;
//Adds a new listNode to the rear of the queue.
public void enqueue(String data) {
listNode node = new listNode();
node.data = data;
node.next = null;
if (rear != null) {
rear.next = node;
} else {
rear = node;
front = node;
}
rear = node;
}
// Returns the data carried by the listNode at the front of the queue and removes it from the queue.
public String dequeue() {
if (rear == null) return null;
String rData = front.data;
front = front.next;
return rData;
}
// Returns the front listNode (The next node to be dequeued)
public listNode getFront() {
return front;
}
//Returns the rear listNode (the last node to be enqueued)
public listNode getRear() {
return rear;
}
}
-----------------------------------------------------------------------------------------------
public class Stack {
private listNode top;
//Push method for stack class
public void push(String data) {
listNode node = new listNode();
node.data = data;
node.next = top;
top = node;
}
// Pop method for the stack class
public String pop () {
if(top == null) return null;
String data = top.data;
top = top.next;
return data;
}
// getTop method for stack class
public listNode getTop () {
return top;
}
}
---------------------------------------------------------------------------------------------
public class listNode {
public String data;
public listNode next;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.