How to Evaluate an Expression

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:

1. -
2. +
3. /
4. *

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:

1. Tokenizing the expression (turning the input into a list of symbols and numbers)
2. Converting the tokens to postfix format (where the operator goes after the 2 operands)
3. 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.