An Unconventional Approach to Determine Operator Precedence: Dijkstra’s Two-Stack Algorithm

“Computer science is no more about computers than astronomy is about telescopes.”

― Edsger W. Dijkstra

Ever wondered how computers determine the order of precedence in a complicated expression, with just pointers from left to right? This little algorithm, conceived by the Dutch computer scientist Edsger W. Dijkstra, will shed some light on how we can interpolate a left-to-right iterative process onto a stack, one of the most fundamental data structures in computer science. We will utilize two stacks for this procedure, as the title suggests.

Stacks

Let us start with a little snippet of what stacks are. Stacks, quite literally, are stacks of information. Consider a plate of pancakes, or a stack of books at your favorite coffee shop. You can take one off from the top, but it’s a lot harder to pick one from the bottom or the middle. In computer science, we say that a stack is a data structure that can provide information from the top of its elements, which you may have heard is called a LIFO (last-in, first-out) method. Stacks are particularly useful for this algorithm since we only need elements not from the bottom or in the middle but from the top.

For the two-stack algorithm, we will create a stack called values and a stack called operations. The first one will include the values in the expression and the second one will include algebraic operations such as addition, multiplication, subtraction, etc.

There are various ways to store a multinomial expression in the memory, but we will store the input as a string and remove any whitespaces for simplicity’s sake. Strings are particularly useful for implementation since they are easily iterable, which makes the lucidity of this algorithm stand out.

How It Works

With the basics of our methodology covered, let us now describe how the actual algorithm works. Each step has been enumerated where additional steps are exhibited with code fragments in Python 3. Considering each iterative element denoted by the variable char has already been converted to a string at the beginning, we can easily take the first iterative element char and proceed. The procedure is as follows:

1. If you see a left parenthesis, just ignore it.

if char == “(“:
    pass

2. If char has a numerical value, i.e. it has type int, float, or double (not in Python 3 but Java, for example), place them in the values stack.

try:
   char = int(char)
   values.append(char)

3. If char is an operator, place them in the operators stack.

4. If char is a right parenthesis, take the operation on the top of the operators stack and operate with the top two values (first_value and second_value) in the values stack.

first_value = values.pop()
second_value = values.pop()
operator = operators.pop()

5. Push the value of the operation onto the top of the stack.

Intuitively, one might need to put all the code snippets inside a loop until one of the stacks run out of elements. Since we’re pushing/popping elements from the two stacks as we go, the process takes care of itself and ultimately terminates with a single value in the values stack. This is where the intelligibility of this algorithm can be observed once more.

Limitations

Even though the two-stack algorithm follows a very simple and brilliant procedure, there are some drawbacks one might need to keep in mind. Some of these limitations have been listed below.

Parsing Multi-Digit Integers

Since we are converting the expression to a string and iterating over each of its elements based on their types, the algorithm may fail to differentiate between a single-digit integer and a multi-digit one. Consider 2 + 3 and 20 + 3: the algorithm will iterate over 2 and 0 separately for the second expression. The re module in Python 3 and other libraries can do a great job of parsing integers from strings, but they usually interfere with the sequential flow of the algorithm. There is another limitation induced as a by-product of this implementation, which we will discuss next.

Negative Values

The algorithm cannot differentiate between the operator “–” and the negative sign “–”. If the input expression includes negative values, it would be more useful to use a function similar to copysign() to denote the negative value, or simply assign a different operator to subtraction other than “–”.

Redundant Parentheses

The algorithm uses left and right parentheses to position itself on the input and start an operation. For the algorithm to work correctly, redundant parentheses are required both at the beginning and at the end of the expression, e.g. (2 + (3 * 5)) instead of 2 + (3 * 5). Recall that the right parenthesis is the caller-to-action for the operation at the top of the operators stack.

Conclusion

The order of precedence for complicated operations could be very well-recognized and understood by humans whereas it becomes a little tricky to make a computer interpret this expression and evaluate a correct output. Dijkstra’s Algorithm provides a very compact and clever way to tackle this problem using one of the most fundamental data structures in computer science. It also employs a similar logic to one of the most famous algorithms in computer science and graph theory, Dijkstra’s Shortest Path Algorithm. These two unique strategies provide highly scalable solutions that can be implemented in almost any programming language while minimizing the occurrence of human error.