Categories
Golang

Write a simple calculator with go

What is calculator

Calculator – Wikipedia

So basically, calculator is used to calculate the result after apply different operations on numbers.

The things that made up the calculation expression

assume we have an calculation expression: (1+2)*(10 / 5) - 3

we can see that there are serveral kinds of things:

  • left parenthesis
  • right parenthesis
  • numbers
  • operators, like +, *, -, /

we can call these things the tokens. these tokens made up the calculation expressions.

The Precedence of operators

When we calculate, must consider the precedence of operators, the precedence will affect the final result of the expression.

for (1+2)*(10 / 5) - 3 the calculation process is:

  1. scan the expression from left to right. when we meet the right parenthesis then will calculate (1+2) first, because right parenthesis has the highest precedence in calculation.
  2. calculate the (10 / 5) = 2
  3. calculate the result of 3 * 2, because * has higher precedence than -
  4. calculate 6 - 3 = 3, get the final result.
  5. when there are 2 operator has the same precedence, we calculate from left to right.

So we have a table of precedence of operators we will support.

operatorprecedence
)3
*2
/2
+1
1
(0

The stack

We will use 2 stack to store the operators and operands.

let’s go through the calculation process with the operator and operands stack.

expression: (1+2)*(10 / 5) - 3

init state of expression

0123456789101112
(1+2)*(10/5)3

operator stack and operands stack:

operator: []
operands: []

read at expression index 0:

( is an operator with the lowest precedence, So put it to the operator stack.

operator: ['(']
operands: []

read expression index 1:, encounter number 1, so put it to operands stack.

operator: ['(']
operands: [1]

read expression index 2: + has higher precedence than (, so put it to operator stack.

operator: ['(', '+']
operands: [1]

read expression index 3: value 2 is number so, put it to operands stack.

operator: ['(', '+']
operands: [1, 2]

read expression index 4:

we meet right parenthesis, So we will pop operator util meet the left parenthesis.

4.1 pop + from operator stack, and pop 2 numbers from operands stack.

operator: ['(']
operands: []

4.2calculate the + result and push the result to operands stack.

operator: ['(']
operands: [3]

4.3 pop left parenthesis

operator: []
operands: [3]

read index 5 value: *

operator: ['*']
operands: [3]

read index 6 value: (

operator: ['*', '(']
operands: [3]

read index 7 value: 10

operator: ['*', '(']
operands: [3, 10]

read index 8 value: /, since / has higher precedence, So push it to operator stack.

operator: ['*', '(', '/']
operands: [3, 10]

read index 9 value: 5

operator: ['*', '(', '/']
operands: [3, 10, 5]

read index 10 value: ), pop operator stack util meet left parenthesis.

10.1 pop /, and pop number 10, 5

operator: ['*', '(']
operands: [3]

10.2push the value of 10 / 5=2 to operands stack

operator: ['*', '(']
operands: [3, 2]

10.3 pop the left parenthesis.

operator: ['*']
operands: [3, 2]

read expression value at index: 11, – has lower precedence , pop * from the operator stack, pop 3 and 2 from operands stack.

operator: []
operands: []

and push the result of 3 * 2back to operands stack.

operator: []
operands: [6]

push - to operator stack back.

operator: ['-']
operands: [6]

read expression value at index: 12

0123456789101112
(1+2)*(10/5)3
operator: ['-']
operands: [6, 3]

Finally, pop the last ‘-‘ operator from operator stack, and calculate the final result.

operator: []
operands: [3]

So finally we get the calculation result: 3

Leave a Reply

Your email address will not be published. Required fields are marked *