This tutorial teaches **how to evaluate an expression**.

## Making the Custom Block

This implementation does not include support for functions or unary negation. This means if you want to calculate `-5 * 10`

you will have to rephrase it as `(0-5) * 10`

### Variables needed

You will need to create these Variables:

(i)

(last token)

(token)

(letter)

(result)

You will also need to create these Lists:

(queue::list)

(stack::list)

(tokens::list)

Note: | Make sure these operators are in the exact same order in the list. |

And a list called operators with these items:

- -
- +
- /
- *

### Full block

This Project has the script for easy backpacking.

define evaluate (expression) set [i v] to (1) // Tokenize the expression delete all of [tokens v] repeat (length of (expression)) set [letter v] to (letter (i) of (expression)) set [last token v] to (item (length of [tokens v]) of [tokens v]) if <(123456.7890) contains (letter)> then if <<((last token) / (1)) = (last token)> or <(last token) = [.]>> then replace item (length of [tokens v]) of [tokens v] with (join (last token) (letter)) else add (letter) to [tokens v] end else if <[()+-/*] contains (letter)> then add (letter) to [tokens v] end end end delete all of [stack v] // Shunting yard algorithm delete all of [queue v] set [i v] to (1) repeat (length of [tokens v]) set [token v] to (item (i) of [tokens v]) if <((token) / (1)) = (token)> then add (token) to [queue v] end if <[operators v] contains (token)> then repeat until <<<(item (1) of [stack v]) = [(]> or <(length of [stack v]) = [0]>> or <(item # of (item (1) of [stack v]) in [operators v]) < (item # of (token) in [operators v])>> add (item (1) of [stack v]) to [queue v] delete (1) of [stack v] end insert (token) at (1) of [stack v] end if <(token) = [(]> then insert (token) at (1) of [stack v] end if <(token) = [)]> then repeat until <<(item (1) of [stack v]) = [(]> or <(length of [stack v]) = [0]>> add (item (1) of [stack v]) to [queue v] delete (1) of [stack v] end if <(item (1) of [stack v]) = [(]> then delete (1) of [stack v] end end change [i v] by (1) end repeat until <(length of [stack v]) = (0)> add (item (1) of [stack v]) to [queue v] delete (1) of [stack v] end repeat until <(length of [queue v]) = [0]> // Stack machine set [token v] to (item (1) of [queue v]) delete [1] of [queue v] if <[operators v] contains (token)> then if <(token) = [+]> then insert ((item [2] of [stack v]) + (item [1] of [stack v])) at [1] of [stack v] end if <(token) = [-]> then insert ((item [2] of [stack v]) - (item [1] of [stack v])) at [1] of [stack v] end if <(token) = [/]> then insert ((item [2] of [stack v]) / (item [1] of [stack v])) at [1] of [stack v] end if <(token) = [*]> then insert ((item [2] of [stack v]) * (item [1] of [stack v])) at [1] of [stack v] end delete [2] of [stack v] delete [2] of [stack v] else insert (token) at (1) of [stack v] end end set [result v] to (item [1] of [stack v]) // The answer will be stored in the result variable

## Explanation

The problem of evaluating an expression can be broken down into 3 steps:

- Tokenizing the expression (turning the input into a list of symbols and numbers)
- Converting the tokens to postfix format (where the operator goes after the 2 operands)
- Evaluating the postfix expression with a stack machine (calculating the answer)

#### Tokenizing the expression

The expression must first be converted into a list. Every number must have all its digits in the same list element.

This script will tokenize an expression:

set [i v] to (1) delete all of [tokens v] repeat (length of (expression :: custom)) set [letter v] to (letter (i) of (expression :: custom)) set [last token v] to (item (length of [tokens v]) of [tokens v]) if <(123456.7890) contains (letter)> then if <<((last token) / (1)) = (last token)> or <(last token) = [.]>> then replace item (length of [tokens v]) of [tokens v] with (join (last token) (letter)) else add (letter) to [tokens v] end else if <[()+-/*] contains (letter)> then add (letter) to [tokens v] end end

#### Converting the tokens to postfix format

Next the Shunting yard algorithm is used to convert the tokens from infix (A op B) to postfix (A B op). This is done because it's a lot less code to calculate a postfix expression than an infix one.

This script will run the shunting yard algorithm on the tokens list:

**Make sure the operators list is in the right order! (-, +, /, *)**:

delete all of [stack v] delete all of [queue v] set [i v] to (1) repeat (length of [tokens v]) set [token v] to (item (i) of [tokens v]) if <((token) / (1)) = (token)> then add (token) to [queue v] end if <[operators v] contains (token)> then repeat until <<<(item (1) of [stack v]) = [(]> or <(length of [stack v]) = [0]>> or <(item # of (item (1) of [stack v]) in [operators v]) < (item # of (token) in [operators v])>> add (item (1) of [stack v]) to [queue v] delete (1) of [stack v] end insert (token) at (1) of [stack v] end if <(token) = [(]> then insert (token) at (1) of [stack v] end if <(token) = [)]> then repeat until <<(item (1) of [stack v]) = [(]> or <(length of [stack v]) = [0]>> add (item (1) of [stack v]) to [queue v] delete (1) of [stack v] end if <(item (1) of [stack v]) = [(]> then delete (1) of [stack v] end end change [i v] by (1) end repeat until <(length of [stack v]) = (0)> add (item (1) of [stack v]) to [queue v] delete (1) of [stack v] end

#### Calculating the result with a stack machine

This script will calculate the result of the postfix expression:

repeat until <(length of [queue v]) = [0]> set [token v] to (item (1) of [queue v]) delete [1] of [queue v] if <[operators v] contains (token)> then if <(token) = [+]> then insert ((item [2] of [stack v]) + (item [1] of [stack v])) at [1] of [stack v] end if <(token) = [-]> then insert ((item [2] of [stack v]) - (item [1] of [stack v])) at [1] of [stack v] end if <(token) = [/]> then insert ((item [2] of [stack v]) / (item [1] of [stack v])) at [1] of [stack v] end if <(token) = [*]> then insert ((item [2] of [stack v]) * (item [1] of [stack v])) at [1] of [stack v] end delete [2] of [stack v] delete [2] of [stack v] else insert (token) at (1) of [stack v] end end set [result v] to (item [1] of [stack v])

## Using the Custom Block

when green flag clicked evaluate [5 + 5] :: custom say (return)

If it worked, your sprite should say 10.