Calculating with Reverse Polish notation (RPN) #

Watch the video for an introduction to the concepts.

Reverse polish notation doesn’t have anything to do Flutter. Here we are just using it to practice some writing Dart. And learning about stack, because that becomes important later for navigation in apps.

The Calculator app on macOS in RPN mode

Description #

Implement a simple calculator based on Reverse Polish Notation (RPN). RPN is also known as postfix notation.

We are used to what is called infix notation where the operator is between the operands. With postfix notation, the operator follows the operands. RPN has the advantage of not using parentheses. Values entered are stored in a stack.

Picture a stack of cards

• You put a card in the stack by placing it on top of other cards.
• You can remove a card by taking the topmost card.
• You can also peek at the card in the top of the stack.

Create a project #

Open a terminal. Use cd to navigate to the folder where you want to store your project. Then create a new Dart project with:

dart create rpn_calculator

It will create a sub-folder called rpn_calculator/. Open it in Android Studio.

In the project you will see the following files:

├── analysis_options.yaml
├── bin
│   └── rpn_calculator.dart
├── CHANGELOG.md
├── lib
│   └── rpn_calculator.dart
├── pubspec.lock
├── pubspec.yaml
├── README.md
└── test
    └── rpn_calculator_test.dart

The main() function (entry point for the program) is defined in /bin/rpn_calculator.dart. All your logic (command implementations) should be added to files in the lib/ folder. You can ignore all other files and folders for now.

Implementation #

Base your stack on the List class. The end of the list, should represent the top of the stack.

Stacks support 3 operations.

An operation (+, -, *, / etc) replaces values in the stack with the result. You can support more operations if you want.

You will also need an operation to push a value to the stack.

Operations should implement using the Command pattern, or variation thereof.

Make a class for each operation. They should all implement the same Command interface.

Remember: in Dart we can use an abstract class when we need just an interface.

abstract class Command {
  void execute(List<num> stack);
}

You should implement Command in a subclass for each operation.

class AddCommand implements Command {
  @override
  void execute(List<num> stack) {
    // implementation goes here
  }
}

Can you find a way to implement undo functionality? Maybe you need another stack for it?

What about UI? #

So you have a bunch of classes. That’s not really useful. You might be thinking “how do I make a GUI for it”. I will show you that in an upcoming chapter. For now, you could try to make a CLI for it.

Here is an example of how you can read input and print output in a CLI app.

import 'dart:io';

void main()
{
    print("Enter your name?");
    String? name = stdin.readLineSync();
    print("Hello, $name!");
}

Importing 'dart:io' allows you to get line of text input using stdin.readLineSync().

What about infix notation? #

Implementing a calculator based on infix notations requires that the input gets converted into a tree structure that then gets recursively evaluated to calculate a result.

Here is a video from Computerphile YouTube channel showing how to implement it in Python.