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

Note that the expression can be entered with or without spaces separating the operators and operands. For
instance, if the expression in the sample run were entered as follows, the correct postfix form would be produced:
(7 - 8/2/ 2)*((7-2) *3 - 6)
Program P4.5 assumes that the given expression is a valid one. However, it can be easily modified to recognize
some kinds of invalid expressions. For instance, if a right bracket is missing, when we reach the end of the expression,
there would be a left bracket on the stack. (If the brackets match, there would be none.) Similarly, if a left bracket is
missing, when a right one is encountered and we are scanning the stack for the (missing) left one, we would not find it.
You are urged to modify Program P4.5 to catch expressions with mismatched brackets. You should also modify it
to handle any integer operands, not just single-digit ones. Yet another modification is to handle other operations such
as % , sqrt (square root), sin (sine), cos (cosine), tan (tangent), log (logarithm), exp (exponential), and so on.
4.4.1 Evaluating an Arithmetic Expression
Program P4.5 stores the postfix form of the expression in a character array, post . We now write a function that, given
post , evaluates the expression and returns its value. The function uses the algorithm at the beginning of Section 4.4.
We will need an integer stack to hold the operands and intermediate results. Recall that we needed a character
stack to hold the operators. We can neatly work with both kinds of stacks if we define NodeData as follows:
public class NodeData {
char ch;
int num;
public NodeData(char c) {
ch = c;
}
public NodeData(int n) {
num = n;
}
public NodeData(char c, int n) {
ch = c;
num = n;
}
public char getCharData() {return ch;}
public int getIntData() {return num;}
public static NodeData getRogueValue() {
return new NodeData('$', -999999); //the user will choose which one is needed
}
} //end class NodeData
We use the char field for the operator stack and the int field for the operand stack. Note the three constructors
and the three accessors for setting and retrieving ch and num .