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

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Stack S = new Stack();
System.out.printf("Enter a positive integer: ");
int n = in.nextInt();
while (n > 0) {
S.push(new NodeData(n % 2));
n = n / 2;
}
System.out.printf("\nIts binary equivalent is ");
while (!S.empty())
System.out.printf("%d", S.pop().getData());
System.out.printf("\n");
} //end main
} //end class DecimalToBinary
The following is a sample run of Program P4.4:
Enter a positive integer: 99
Its binary equivalent is 1100011
4.4 How to Convert from Infix to Postfix
One of the classical uses of a stack is in the evaluation of arithmetic expressions. One of the problems with the way
we normally write an arithmetic expression ( infix form) is that it is not convenient for evaluation by a computer. For
such evaluation, one method is to first convert the expression to postfix form. We first show how to do this conversion,
followed by an explanation of how the expression is evaluated.
Consider the expression 7 + 3 * 4. What is its value? Without any knowledge about which operation should
be performed first, we might work out the value from left to right as (7 + 3 = 10) * 4 = 40. However, normal rules of
arithmetic state that multiplication has higher precedence than addition. This means that, in an expression like
7 + 3 * 4, multiplication (*) is performed before addition (+). Knowing this, the value is 7 + 12 = 19.
We can, of course, force the addition to be performed first by using brackets, as in (7 + 3) * 4. Here, the brackets
mean that + is done first.
These are examples of infix expressions; the operator (+, *) is placed between its operands. One disadvantage of
infix expressions is the need to use brackets to override the normal precedence rules .
Another way of representing expressions is to use postfix notation. Here, the operator comes after its operands
and there is no need to use brackets to specify which operations to perform first. For example, the postfix form of
7 + 3 * 4 is 7 3 4 * +
and the postfix form of
(7 + 3) * 4 is 7 3 + 4 *
One useful observation is that the operands appear in the same order in both the infix and postfix forms but they
differ in the order and placement of the operators.
Why is postfix notation useful? As mentioned, we do not need brackets to specify precedence of operators. More
importantly, though, it is a convenient form for evaluating the expression.