Lab05: // infix.java import java.io.*; import MyStackQueue.*; class infix { stat
ID: 3588396 • Letter: L
Question
Lab05:
// infix.java
import java.io.*;
import MyStackQueue.*;
class infix {
static Queue infixToPostfix(String s) {
Tokenizer token = new Tokenizer(s);//step3
Queue queue = new Queue();
Token tkn = token.nextToken();//step5
Stack theStack = new Stack();//step 1
theStack.push(new Operator('#'));//step2
while(tkn != null) {//step4
if(tkn instanceof Operand) {//step8
queue.enqueue(tkn);
} else {
Operator Opr = (Operator)tkn;
if(Opr.operator == '(') {//step9
theStack.push(Opr);
} else if(Opr.operator == ')') {
while (((Operator)theStack.top()).operator != '(') {
queue.enqueue(theStack.pop());//step6
}
theStack.pop();
} else {
while (((Operator)theStack.top()).precedence() >= (Opr.precedence())) {
queue.enqueue(theStack.pop());
}
theStack.push(Opr);
}
}
tkn = token.nextToken();
}
while(((Operator)theStack.top()).operator != '#') {//step11
queue.enqueue(theStack.pop());
}
theStack.pop();
return queue;
}
static int evaluePostfix(Queue Post) {
Stack theStack = new Stack();
int result= 0;
while(!Post.isEmpty()) {
Token tkn = (Token)Post.dequeue();
if(tkn instanceof Operand) {
theStack.push(tkn);
}
else if(tkn instanceof Operator) {
Operator Opr = (Operator)tkn;
int opnd2= (int)((Operand)theStack.pop()).operand;
int opnd1= (int)((Operand)theStack.pop()).operand;
switch(Opr.operator) {//step 10 to perform an operation
case('+'): result = opnd1 + opnd2; break;
case('-'): result = opnd1 - opnd2; break;
case('*'): result = opnd1*opnd2; break;
case('/'): result = opnd1/opnd2; break;
}
theStack.push(new Operand(result));
}
}
return result;
}
public static void main(String[] args) throws IOException {
Queue Post;
while(true) {
System.out.print("Enter infix: ");
System.out.flush();
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
if ( s.equals("") ) break;
Post = infixToPostfix(s);
System.out.println("Postfix is " + Post.toString() + ' ');
int result = evaluePostfix(Post);
System.out.println("Result is " + result + ' ');
}
}
In your lab05, replace instructor’s Tokenizer class and MyStackQueue package with your own.
Requirements:
1. You must use a linked list to implement your queue. 2. You must use an array to implement your stack. 3. You must use the following frame work to implement your tokenizer.
class Tokenizer { private char [] Buf; private int cur;
Tokenizer(String infixExpression) { Buf = infixExpression.toCharArray(); cur = 0; }
boolean moreTokens() { Skip blanks. return cur<Buf.length; }
Token nextToken() { 1. Skip blanks.
2. if (cur>=Buf.length) return null;
3. If the next character is a digit, keep reading until a non-digit is read. Convert the string of digits into an integer.
String Digits = new String(Buf, start, len); int num = Integer.valueOf(Digits).intValue();
Use num to create and return an operand.
4. Otherwise, use the next character to create and return an operator.
}
}
Explanation / Answer
infix.java
import java.io.*;
import MyStackQueue.*;
class infix {
static Queue infixToPostfix(String s) {
Tokenizer token = new Tokenizer(s);//step3
Queue queue = new Queue();
Token tkn = token.nextToken();//step5
Stack theStack = new Stack();//step 1
theStack.push(new Operator('#'));//step2
while(tkn != null) {//step4
if(tkn instanceof Operand) {//step8
queue.enqueue(tkn);
} else {
Operator Opr = (Operator)tkn;
if(Opr.operator == '(') {//step9
theStack.push(Opr);
} else if(Opr.operator == ')') {
while (((Operator)theStack.top()).operator != '(') {
queue.enqueue(theStack.pop());//step6
}
theStack.pop();
} else {
while (((Operator)theStack.top()).precedence() >= (Opr.precedence())) {
queue.enqueue(theStack.pop());
}
theStack.push(Opr);
}
}
tkn = token.nextToken();
}
while(((Operator)theStack.top()).operator != '#') {//step11
queue.enqueue(theStack.pop());
}
theStack.pop();
return queue;
}
static int evaluePostfix(Queue Post) {
Stack theStack = new Stack();
int result= 0;
while(!Post.isEmpty()) {
Token tkn = (Token)Post.dequeue();
if(tkn instanceof Operand) {
theStack.push(tkn);
}
else if(tkn instanceof Operator) {
Operator Opr = (Operator)tkn;
int opnd2= (int)((Operand)theStack.pop()).operand;
int opnd1= (int)((Operand)theStack.pop()).operand;
switch(Opr.operator) {//step 10 to perform an operation
case('+'): result = opnd1 + opnd2; break;
case('-'): result = opnd1 - opnd2; break;
case('*'): result = opnd1*opnd2; break;
case('/'): result = opnd1/opnd2; break;
}
theStack.push(new Operand(result));
}
}
return result;
}
public static void main(String[] args) throws IOException {
Queue Post;
while(true) {
System.out.print("Enter infix: ");
System.out.flush();
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
if ( s.equals("") ) break;
Post = infixToPostfix(s);
System.out.println("Postfix is " + Post.toString() + ' ');
int result = evaluePostfix(Post);
System.out.println("Result is " + result + ' ');
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.