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 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:

Note 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.

Cookies help us deliver our services. By using our services, you agree to our use of cookies.