Three applications of stacks are presented here. These examples are central to many activities that a computer must do and deserve time spent with them.
In particular we will consider arithmetic expressions. Understand that there are boolean and logical expressions that can be evaluated in the same way. Control structures can also be treated similarly in a compiler.
This study of arithmetic expression evaluation is an example of problem solving where you solve a simpler problem and then transform the actual problem to the simpler one.
Aside: The NP-Complete problem. There are a set of apparently intractable problems: finding the shortest route in a graph (Traveling Salesman Problem), bin packing, linear programming, etc. that are similar enough that if a polynomial solution is ever found (exponential solutions abound) for one of these problems, then the solution can be applied to all problems.
We are accustomed to write arithmetic expressions with the operation between the two operands: a+b or c/d. If we write a+b*c, however, we have to apply precedence rules to avoid the ambiguous evaluation (add first or multiply first?).
There's no real reason to put the operation between the variables or values. They can just as well precede or follow the operands. You should note the advantage of prefix and postfix: the need for precedence rules and parentheses are eliminated.
| Infix | Prefix | Postfix |
|---|---|---|
| a + b | + a b | a b + |
| a + b * c | + a * b c | a b c * + |
| (a + b) * (c - d) | * + a b - c d | a b + c d - * |
| b * b - 4 * a * c | ||
| x * x + y / (z -1) | ||
| 40 - 3 * 5 + 1 |
Postfix expressions are easily evaluated with the aid of a stack.
Assume we have a string of operands and operators, an informal, by hand process is
The time complexity is O(n) because each operand is scanned once, and each operation is performed once.
A more formal algorithm:
create a new stack
while(input stream is not empty){
token = getNextToken();
if(token instanceof operand){
push(token);
} else if (token instance of operator) {
op2 = pop();
op1 = pop();
result = calc(token, op1, op2);
push(result);
}
}
return pop();
Demonstration with 2 3 4 + * 5 -
and 5 7 + 6 2 - *
This process uses a stack as well. We have to hold information that's expressed inside parentheses while scanning to find the closing ')'. We also have to hold information on operations that are of lower precedence on the stack. The algorithm is:
This algorithm doesn't handle errors in the input, although careful analysis of parenthesis or lack of parenthesis could point to such error determination.
Apply the algorithm to the above expressions.
Backtracking is used in algorithms in which there are steps along some path (state) from some starting point to some goal.
In all of these cases, there are choices to be made among a number of options. We need some way to remember these decision points in case we want/need to come back and try the alternative
Consider the maze. At a point where a choice is made, we may discover that the choice leads to a dead-end. We want to retrace back to that decision point and then try the other (next) alternative.
Again, stacks can be used as part of the solution. Recursion is another, typically more favored, solution, which is actually implemented by a stack.
Any modern computer environment uses a stack as the primary memory management model for a running program. Whether it's native code (x86, Sun, VAX) or JVM, a stack is at the center of the run-time environment for Java, C++, Ada, FORTRAN, etc.
The discussion of JVM in the text is consistent with older and modern OS such as Windows NT 8 or 10, Solaris, Unix/Linux runtime environments.
Each program that is running in a computer system has its own memory allocation containing the typical layout as shown below. [Thread management has a variant of this.]
When a method/function is called
While the method executes, the local variables and parameters are simply found by adding a constant associated with each variable/parameter to the Base Pointer.
When a method returns
There is also a Stack Pointer that allow other temporary use of the stack above the top AR.