Write Your Own Calculator

This is the solution for Calculator Challenge implemented using Go.

Idea

Parsing is the process by which a compiler turns a sequence of tokens into a tree representation:

                            Add
                 Parser     / \
'1 + 2 * 3'    ------->    1  Mul
                              / \
                             2   3

We are to take prompts like:

    calc '1 + 2 * 3'

and return the result.

Operation precedence are taken cared using binding power like below:

  
Equation            -   1     +     3   *   2   ^   2
                   / \       / \       / \     / \
Binding power         5     1   2     3   4   6   7
                     rbp   lbp  rbp

In each loop we compare lbp and the passed-in min_bp. If lbp is greater, the operator has higher priority.

Implementation Steps

1. Create a lexer that tokenizes the input.
2. Create a parser that parses the tokens, and turn the tokens into an AST. To build the AST, I selected Pratt Parsing and S-Expression instead of using the Shunting Yard algorithm and stacks.
3. Evaluate the AST and output the calculated results.

Program

Git pull the repo and run the program.

   go run main.go

or compile it first then run the corresponding executable on different platforms.

  # On Linux or MacOS
  go build -o calculator
  ./calculator
  
  # On Windows
  env GOOS=windows GOARCH=amd64 go build -o calculator.exe
  calculator.exe

You can also run the existing binaries pulled directly from the repo.

  # On Linux
  
  ./calculator
  
  # On Windows
  calculator.exe

After starting the program you'll see:

    Calculator Started.
    >>>> Input your calculator prompt in format - calc '<your equation here>'
    >>>> Or type help to see instructions.
    >> Insert your prompt:

There are two types of prompt:

1. Calculator prompts
2. Quit prompts

Prompt Example:

This is the general input format the calculator will take:

   // 1. Calculator prompt, white space ignored, case-insensitive.
   calc '5 + 2 * 3'

To quit the calculator:

  // 2. Quit prompt, case insensitive.    
  quit  

Features

• Float supports

      calc '2.1 * 3.5'

• Four simple expressions:

    calc '1 + 2' // result: 3.0000
    calc '2 - 1' // result: 1.0000
    calc '2 * 3' // result: 6.0000
    calc '3 / 2' // result: 1.5000

• Power with ^

    // Power with integers 
    calc '2 ^ 3'        // result: 6.0000
    calc '5.5 ^ 6'      // result: 27680.6406
    calc '-1 ^ 4'       // result: -1.0000
    calc '(-1) ^ 4'     // result: 1.0000

• Mixed operations:

    calc '1 + 2 * 3'             // result: 7.0000
    calc '3 * 7 + 5 * 4'         // result: 41.0000
    calc '3 * 7 + 2 ^ 4 - 7 ^ 0' // result: 36.0000

  The result is rounded to 4 decimal places.

• Brackets:

    calc '(1 + 2) * 3'                              // result: 9.0000
    calc '[(1 + 2) * 3] * 4'                        // result: 36.0000
    calc '{[(1 + 2) * 3] + 4} * 5'                  // result: 65.0000
    calc '{[(1 + 2) * 3] * [(100 / 20) + 8]} - 123' // result: -6.0000
  
    // Also supports equations with all parenthesis.
    calc '(((1 + 2) * 3) + 4) * 5'                  // result: 65.0000

  Mixed operations of brackets and ^ are handled.

    // Should be different
    calc '-1 ^ 4'   // result: -1.0000
    calc '(-1) ^ 4' // result: 1.0000

  • Bracket expressions like below should cause error (unbalanced brackets):

        calc '(1 + 2 * 3'
        calc '1 + 2) * 3'
    
        calc '[(1 + 2 * 3] * 4'
        calc '[1 + 2) * 3] * 4'
        calc '[(1 + 2) * 3 * 4'
    
        calc '{1 + 2) * 3] + 4} * 5'

• Store previous result in ans.

    // First prompt
    calc '1 + 2'        // result: 3.0000
        
    // The current 'ans' is 36.00
    calc 'ans'          // result: 36.0000
            
    // use 'ans' to called stored results
    calc 'ans * 12'     // result: 36.0000

• Clear (AC button).

    // First prompt
    calc '1 + 2'        // result: 3.0000
   
    // use 'ans' to call stored results
    calc 'ans * 12'     // result: 36.0000
   
    // The current 'ans' is 36.00
    calc 'ans'          // result: 36.0000
   
    // Clear 'ans'
    clear
   
    // The current 'ans' is 0.0000
    calc 'ans'          // result: 0.0000 

References

Tools:

• AST Explorer

Video:

• Swift 3 Fun Algorithms: Abstract Syntax Tree

Reads:

• Wikipedia: Shunting yard algorithm
• Wikipedia: S-expression
• Simple but Powerful Pratt Parsing
• How Desmos uses Pratt Parsers
• Pratt Parsers: Expression Parsing Made Easy
• Arrow functions break JavaScript parsers
• 手寫一個Parser - 代碼簡單而功能強大的Pratt Parsing