Просмотр кода страницы 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 <code>-5 * 10</code> you will have to rephrase it as <code>(0-5) * 10</code>

=== Variables needed ===

You will need to create these [[Variables]]:
* <scratchblocks>(i)</scratchblocks>
* <scratchblocks>(last token)</scratchblocks>
* <scratchblocks>(token)</scratchblocks>
* <scratchblocks>(letter)</scratchblocks>
* <scratchblocks>(result)</scratchblocks>

You will also need to create these [[List]]s:
* <scratchblocks>(queue::list)</scratchblocks>
* <scratchblocks>(stack::list)</scratchblocks>
* <scratchblocks>(tokens::list)</scratchblocks>
{{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 [[projects:470377439|Project]] has the script for easy backpacking.

<scratchblocks>
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
</scratchblocks>

== 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:
<scratchblocks>
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
</scratchblocks>


==== Converting the tokens to postfix format ====
Next the [[wikipedia:Shunting yard algorithm|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! (-, +, /, *)}}
<scratchblocks>
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
</scratchblocks>


==== Calculating the result with a stack machine ====

This script will calculate the result of the postfix expression:

<scratchblocks>
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])
</scratchblocks>

== Using the Custom Block ==
<scratchblocks>
when green flag clicked
evaluate [5 + 5] :: custom
say (return)
</scratchblocks>

If it worked, your sprite should say 10.

[[Category:Math Tutorials]] [[Category:Scripting Tutorials]]