Software Design Using C++

STL: Stacks

The Stack Class

Examples

Reversing a Sequence

stack<int> IntStack;

Pushing an integer onto the stack is then quite easy. The code is as follows:

IntStack.push(Num);

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 stack class pop function does not do this; it only modifies the stack by removing one item from the top. To get the item itself you must first use the top function as shown below. Then you can call the pop function to remove the item.

while (! IntStack.empty())
   {
   Num = IntStack.top();
   IntStack.pop();
   cout << Num << endl;
   }

Converting an Infix Expression to Postfix

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 TakesPrecedence contains the precedence rules. Obviously ^ takes precedence over *, /, + and -. The * and / operators take precedence over + and -. Also, * and / take precedence over themselves, so that a/b*c, for example, is seen as (a/b)*c, not a/(b*c). That is, the operators are handled in left to right order. Similarly, + and - take precedence over themselves in order to again give left to right evaluation in an expression such as a-b-c. However, note that ^ does not take precedence over itself. That is because an expression such as a^b^c must be handled right to left, according to the rules of arithmetic, giving in effect a^(b^c).

Note how convenient the STL is for constructing this algorithm. Both the infix and postfix expressions are handled as objects of the string container class. That allows us, for example, to easily append a symbol to the end of the postfix expression. The stack container class is used to create the needed stack of characters (the saved operators).

See the references for more information.

Related Item