How to Evaluate an Expression: различия между версиями
м |
Patarakin (обсуждение | вклад) м (1 версия импортирована) |
Текущая версия на 11:33, 21 июля 2022
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 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:
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.