Software Design Using C++STL: StacksThe Stack ClassThe stack class is technically a container adaptor
that utilizes some underlying container (by default, a deque, a double-ended
queue) to hold its data. This container adaptor, however, keeps the programmer
from accessing the data in many of the ways that the underlying container
supports; only reasonable types of stack access are allowed. In particular,
container adaptors do not allow you to use iterators. We will not go further
into the details of container adaptors here.
The stack header file needs to be included to use this class.
The class member functions that are provided are listed below. Further
details are provided in the example programs that follow.
ExamplesReversing a SequenceOur 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
Converting an Infix Expression to PostfixOur 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. Related ItemStacks Intermediate Topic. Back to the main page for Software Design Using C++ |