Objective:

The objective of this lab is to get you some experience in using stacks, queues, class packages and UML.

The programming assignment:

In this lab, you are to write an infix evaluator. Given an input string of characters like

12+34*(56-7)-18/9, first print the postfix equivalent 12 34 56 7 - * + 18 9 / - and then print the value of the expression.

Notes: In this lab,

You must use the algorithms given in class to convert infix expressions to postfix expressions and to evaluate postfix expressions.

You must use the instructors stack and queue package.

You must use the instructors frame work depicted by the following class diagrams.

Complete methods infixToPostfix and evaluatePostfix.

Some programming Hints:

To create a stack:

Stack theStack = new Stack();

To push # into the stack:

theStack.push(new Operator(#));

To create a Tokenizer from a string s:

Tokenizer T = new Tokenizer(s);

Repeat until no more tokens:

While (T.moreTokens()) { ..}

To get the next token:

Token Tkn = T.nextToken();

To pop a token into a variable of the type Token:

Token Current = (Token) theStack.pop();

To cast a Token into an Operator:

Opr = (Operator)Tkn;

To check if a Token variable Tkn contains an Operand:

if (Tkn instanceof Operand)

To check if an operator is a (:

if (Opr.operator==()

To perform an operation:

switch(Opr.operator) { case +: result = opnd1 + opnd2; break;

}

To check the operator on the top of the stack:

((Operator)theStack.top()).operator

-----------------------------------------------------------------------------------------------------------------------

// infix.java import java.io.*; import MyStackQueue.*;

class infix { static Queue infixToPostfix(String s) { }

static int evaluePostfix(Queue Post) { }

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 + ' '); } } }

MyStackQueue Stack Token ueue +Stack Il Constructor+Queue0 I Constructor +push(e:Object) +pop:Object +top0: Object +isEmptv0: boolean +enqueue(e:Object) +dequeue0: Object +isEmpty0: boolean +toString0: Strin Operator and +operator: char +Operator(char:opr+Operand(int:opnd) +precedence0: int +toStr toperand: int +oString0: Strin Strin pre pro uses uses creates creates Tokenizer InfixEvaluator (Cab05) +maino infixToPostfix String s): Queue evaluePostfix(Queue Post): int +Tokenizer(String s) +moreTokens0:boolean +nextToke : Token