Skip to content

Latest commit

 

History

History
67 lines (43 loc) · 3.81 KB

IMPLEMENTATION.md

File metadata and controls

67 lines (43 loc) · 3.81 KB
Raw

Implementation

This document will describe the app structure, implementation of the shunting-yard algorithm, infix vs postfix notation, postfix evaluation and custom data structures.

Structure

The app is a CLI (command line interface) tool that takes a mathematical expression written in natural notation as input and outputs the result of the expression. Internally, it uses the shunting-yard algorithm to convert the expression to postfix notation and then evaluates the postfix expression using a custom parser to get the result.

You can see all the available commands by running:

poetry run poe --help

Shunting-yard algorithm

The shunting-yard algorithm is a method for parsing mathematical expressions written in infix notation. It was invented and published by Edsger Dijkstra in 1961 and named after its operation resembles a railroad shunting yard. The algorithm can be explained in the following steps:

  1. Read the input: 3 + 4
  2. Push 3 to the output queue
  3. Check the operator + and compare it to the operator stack
  4. Push the operator + to the operator stack
  5. Push 4 to the output queue
  6. Pop the operators from the operator stack to the output queue
  7. Output queue: 3 4 +

Now the infix notation (3 + 4) is converted to postfix notation (3 4 +) and can be evaluated.

Operator precedence

In step 3, the algorithm checks the precedence of the operators. If the operator on the top of the stack has higher precedence than the operator that is being read, the operator on the top of the stack is popped to the output queue before the new operator is pushed to the stack. This is done until the operator on the top of the stack has lower precedence than the new operator.

The algorithm is implemented in the classes/shunting_yard.py file.

YouTube: "Comp Sci in 5: Shunting Yard Algorithm"

Infix vs Postfix notation

Infix and Postfix are mathematical notations, that offer different ways of writing expressions. In Infix, operators are between operands. This is also sometimes called the conventional mathematical order or the natural notation.

Using Postfix, or Reverse Polish Notation, the operators are after operands. The advantage of postfix notation is that it removes the need for parenthesis and is easier to calculate.

Postfix evaluation

The postfix notation is evaluated using a custom parser that can be found in classes/rpn_evaluator.py. The parser uses a stack to keep track of the operands and operators. The algorithm can be explained in the following steps:

  1. Read the input: 3 4 +
  2. Push 3 and 4 to the stack
  3. Read the operator +
  4. Pop 4 and 3 from the stack
  5. Evaluate 3 + 4 and push the result 7 to the stack
  6. The stack contains exactly one item and the result 7

YouTube: "Comp Sci in 5: Post Fix Stack Evaluator"

Custom data structures

The app uses two custom data structures: Stack and Queue that can be found in classes/stack.py and classes/queue.py respectively. Both are implemented using Python's built-in queue structure. There are also helper classes such as TokenList and MalformedExpressionError that are used to handle the input and errors.

Sources