What are stack based calculators?

Stack is an abstract data type that holds a collection of data and enables to perform certain operations on it in particular order. That order is called LIFO (Last In First Out) which means that the last element that is put into collection will be the first element to get out. A typical stack has two main operations: push and pop; where push function adds an item to the stack and the pop function removes the last element that was pushed to the stack and returns it.

LIFO Stack ( https://en.wikipedia.org)

Stacks has many applications starting from memory management to real life and it is a fundamental (and simple) data structure that must be understood by every single software engineer.

In this article we are going to talk about how arithmetic expressions are evaluated using a Stack.

Postfix expression evaluation

A standard way of writing an arithmetic expression is called infix notation. It is a usual way of how we all are used to write arithmetic expressions: operators are placed in operands and parentheses are used to denote precedence.

Infix notation ( https://introcs.cs.princeton.edu/)

In postfix notation operators follow their operands and surprisingly no parentheses are needed to denote precedence.

Postfix notation ( https://introcs.cs.princeton.edu/)

This notation is also called reverse Polish notation since it is a reverse form of Polish notation which was invented by a Polish logician and philosopher Jan Łukasiewicz and in which operators precede the operands (e.g. +34). Expressions in RPN are unambiguous which means that there is only one way to parenthesize a postfix expression:

postfix to infix conversion ( https://introcs.cs.princeton.edu)

Using a Stack we can evaluate any postfix expression very easily. In fact, very first handheld (pocket) calculator HP-35 which was introduced in 1972 was based on postfix notation. It was confusing to deal with parentheses back then, so people were used to write expressions in postfix notation. And the principle of the calculator was very simple:

• Read the expression from left to right
• If current element is a value (e.g. Integer) push it to the stack
• If current element is an operator, pop last two operands from stack, apply operator and push the result back to the stack

After doing this steps, the very last element that was left in the stack will be our answer. Simple, pop the last element and return it.

RPN evaluation using stack ( https://f-o.org.uk/)

Let’s write this basic but quite powerful and interesting algorithm in JavaScript. Since JavaScript arrays has push and pop methods by default, we can use array instead of implementing our own Stack data type:

RPN expression evaluation using stack with JavaScript

This simple example uses only basic arithmetic operators but you can add as many operators as you want. And if you test it with our previous example it is going to give you the correct result:

evalReversePolish("123+45**+") // output: 101

This particular type of calculator is called stack based calculator and is an example of a stack machine since its working principle is heavily based on Stack abstract data type.

Conclusion

If you were aware of Stack data structure and thinking that it is useless in real life, well, here is the real life use case for you 😉 I hope this article helped you and you were able to learn something. This article is based on Computer Science: Algorithms, Theory, and Machines course on Coursera, so I highly recommend to take that course.

Thanks for reading! If you think this story needs a change, please let me know in comments by also justifying your claim.

Optional challenge

Given an infix expression convert it to postfix notation and evaluate it using stack based calculator that we wrote.