Stacks and Queues - Advanced Topics in Java: Core Concepts in Data Structures - page 124

The operator stack is simply a stack of characters that we will implement using the NodeData class defined at the
end of Section 4.3. This is shown in Program P4.5.
Step 6 of the algorithm requires us to compare the precedence of the operator on top of the stack with the current
operator. This would be easy if we could “peek” at the element on top of the stack without taking it off. To do this, we
write the following instance method, peek , and add it to the Stack class:
public NodeData peek() {
if (!this.empty()) return top.data;
return null;
} //end peek
Putting all these together, we write Program P4.5, which implements the algorithm for converting an infix
expression to postfix. The class Node is the same as that in Program P4.3. The class Stack is the same as that in
Program P4.3 with the addition of peek() .
Program P4.5
import java.io.*;
public class InfixToPostfix {
public static void main(String[] args) throws IOException {
char[] post = new char[255];
int n = readConvert(post);
printPostfix(post, n);
} //end main
public static int readConvert(char[] post) throws IOException {
//Read the expression and convert to postfix. Return the size of postfix.
Stack S = new Stack();
int h = 0;
char c;
System.out.printf("Type an infix expression and press Enter\n");
char token = getToken();
while (token != '\0') {
if (Character.isDigit(token)) post[h++] = token;
else if (token == '(') S.push(new NodeData('('));
else if (token == ')')
while ((c = S.pop().getData()) != '(') post[h++] = c;
else {
while (!S.empty() &&
precedence(S.peek().getData()) >= precedence(token))
post[h++] = S.pop().getData();
S.push(new NodeData(token));
}
token = getToken();
}
while (!S.empty()) post[h++] = S.pop().getData();
return h;
} //end readConvert