Ok, so here's the whopper of the problem. How would one handle order of operations in z80? (I'm actually working in Axe, but its the same jazz)
Imagine I have a string like: ((3x-7) + (x-3))/4x.
What is the best method? I understand string parsing in asm/Axe, and how to test for something in a string. My idea would be, using the above example, to copy something like this into memory:
A: 3x-7
B: x-3
C: 4x
1: A + B
2: 1 / C
Am I on to something?
The usual way to handle parsing problems is by building a syntax tree, then parsing that representation.
Your example would parse into a tree somewhat like this:
Code: (/)
|
/----+----\
| |
(+) (*)
| |
/--+--\ /-+-\
| | | |
(-) (-) 4 x
| |
/-+-\ /-+-\
| | | |
(*) 7 x 3
|
/-+-\
| |
3 x
At which point reducing it is a matter of recursively evaluating operations.
As for generating the tree, you work from a grammar. In this case I might describe it like this:Code: # Variable refs are a single letter
var = [a-z]
# Literal values are integers for simplicity
literal = -?[0-9]+
# Values may be literals or variable references
value = literal | var
# Arithmetic operations
op = [+-*/]
# Parens delimit subtrees
PUSH = '('
POP = ')'
# Expressions may be values, an operation applied to expressions, or a subtree of expressions
expr = value | expr op expr | PUSH expr POP
The tree is then constructed by parsing tokens (the result of lexing) recursively. For regularity we can assume that 'expr op expr' expressions are bracketed by implicit PUSH and POP operations, so the algorithm would go something like this:
- If expression is a value
- Insert value into tree at current location
- If expression is (expr op expr)
- Replace with PUSH expr op expr POP and continue
- If expression is PUSH expr POP
- Insert the result of parsing expr as a subtree
The only remaining part is handling operator precedence, and I can't be bothered to think through that right now. (Sorry 
It should involve defining multiple sets of operators with different precedence in the grammar. Wikipedia also suggests an easy way of rewriting with explicit groups.) Hopefully this is helpful to some extent?
It does help. It helped me come up with an idea that may work.
In ((3x-7) + (x-3))/4x, we know that the /4x will be dealt with last. So we can push 4x onto the "stack". So it now has
4x /
That leaves us with: (3x-7) + (x-3), so then we push (x-3) and (3x-7), so our "stack" looks like
4x /
x-3 +
3x-7
To evaluate, we pop items off our "stack" and evaluate them in the order they occur. That would work in this instance, but not sure how it would hold up against larger chains.
I could store the "stack" sequentially at saferam1.
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.
»
Go to Registration page
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
