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 instructors 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

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.

}

}