Software Design Using C++
The Stack Class
Reversing a Sequence
Our first example, reverse.cpp, uses a stack of integers to reverse a sequence of numbers. Note how the constructor is used to create an empty stack of integers:
Pushing an integer onto the stack is then quite easy. The code is as follows:
What may seem somewhat unusual is how one removes and prints the numbers on
the stack. You may be used to a pop function which somehow returns the item
popped, either via a parameter or in the function name. The
Our second example, convert.cpp, does something more complex: it uses a stack to convert an infix expression to postfix. Recall that in ordinary algebra we use infix expressions, such as (a+b)^2, where the ^ symbol is being used to indicate exponentiation. The corresponding postfix expression is ab+2^, where each operator comes after the two items to which it applies.
The following drawing shows the first few steps of the conversion algorithm. The infix expression is scanned from left to right. Any operand (here taken to be any letter or digit) is copied to the end of the postfix expression. Thus, the operands occur in the same order in the infix and postfix form of any expression. With the operators, one has to worry about precedence rules. A stack is useful here. Parentheses are treated as a type of operator, along with +, -, *, /, and ^. The first operator we encounter, (, is pushed onto the stack. This always occurs with the first operator since we don't yet know if the next operator has a higher priority or not. By the second picture of this drawing, we have reached the + operator. Since the top of stack operator, the (, does not have higher precedence than the +, the + is pushed onto the stack. Then the operand, b, is appended to the developing postfix expression. Now we reach the ) operator. Since the top of stack operator is +, which has higher priority than the ), we now know that it is safe to pop the + and append it to the postfix expression.
Since the top of stack operator is now the (, which does not have higher precedence than the ), we do not copy the ( to the postfix expression. In fact, we have a special case here. When we find matching parentheses, we pop the ( and discard both parentheses. The stack is now empty, and the postfix expression consists of ab+. Next we encounter the ^ operator. Since the stack is empty, the operator gets pushed. The operand, 2, is just copied to the end of the postfix expression. At this point there are no more characters in the infix expression, so a final loop is used to pop any operators from the stack and copy them to the postfix expression. In our example, there is only the ^ to copy to the end of the postfix expression. The drawing below shows these final stages that we have just described:
A useful exercise at this point is to try converting the infix expression ((a+b)^(c*d))-e/f. You should obtain the postfix expression ab+cd*^ef/- as your result. Step through the code for the conversion routine if need be to see how to proceed at each step.
The complete conversion algorithm is contained in the example program,
convert.cpp. Note that the boolean function
Note how convenient the STL is for constructing this algorithm. Both
the infix and postfix expressions are handled as objects of the
See the references for more information.
Back to the main page for Software Design Using C++