Omnimaga
Calculator Community => Other Calc-Related Projects and Ideas => TI Z80 => Topic started by: ACagliano on April 01, 2014, 03:32:42 pm
-
I have been trying to do this myself, but I'm failing. I need to ask for at the least conceptual, if not coding assistance...
I need to make an order of operations parser. For instance, the string: ((3x+7)(x-3))/4x should be evaluated into memory:
3x+7
*
x-3
/
4x
My language is Axe. If there's an app (like Symbolic) that does this, then this post is also an official permission request to view, and perhaps borrow elements from them, if they would help.
-
I recommend you create it with a computer programming language (like lua or python) first so that you can have the concept done and then "port" it to axe because it would be somewhat more difficult to do it initially in axe because axe doesn't come with dynamic arrays (I am not implying that it should though, I like axe how it is.)
-
Ok. The problem is, I don't even know where to start... my initial thought was, starting at position 1 of the input string,
search for a (.
if found, search for next )
copy contents to scrap buffer.
rinse and repeat.
but beyond that, I'm lost...
-
I recommend you create it with a computer programming language (like lua or python) first so that you can have the concept done and then "port" it to axe because it would be somewhat more difficult to do it initially in axe because axe doesn't come with dynamic arrays (I am not implying that it should though, I like axe how it is.)
It would be even more difficult to have to port it from a "high level" language into Axe, so I'd say that coding in Axe direcly is a better idea.
-
You might be right I was just thinking that first he would need to come up with the concept for how to do it but there are lots of ways to do things. There might be some ways that are better in high level programming languages but very difficult in axe.
-
Ok I came up with a partial algorithm, but I may need some assistance coding it. Order of operations goes PEMDAS, so parentheses are first. So, my idea is to loop:
input->A
A->W
While inData(')',A)
;; in the example 3x + (7x + 4x + (3x) - (2x-1))
;; while we have a ), this will keep looping
While inData('(',W)<inData(')',A)
If inData('(',W) < inData(')',A)
inData('(',W) -> Z
End
inData('(',W) + 1 -> W
;; while the next ( we find is in front of the ), we loop.
;; When it moves behind it, we are in a new nested parentheses, so we stop looping.
;; Z is saved, so we can recall correct location.
End
;; Once we are out of the second while loop, we can copy the innermost parentheses...
;; contents to another location in RAM, and zero terminate it, or length pre-pend it.
;; then we delete the contents of that paren from the source string. doing so eliminates that...
;; ), so that the first while loop returns the position of the next ) in its test, so we loop until parens...
;; are all gone.
End
-
bumpity bump
-
Ok I came up with a partial algorithm, but I may need some assistance coding it. Order of operations goes PEMDAS, so parentheses are first. So, my idea is to loop:
input->A
A->W
While inData(')',A)
;; in the example 3x + (7x + 4x + (3x) - (2x-1))
;; while we have a ), this will keep looping
While inData('(',W)<inData(')',A)
If inData('(',W) < inData(')',A)
inData('(',W) -> Z
End
inData('(',W) + 1 -> W
;; while the next ( we find is in front of the ), we loop.
;; When it moves behind it, we are in a new nested parentheses, so we stop looping.
;; Z is saved, so we can recall correct location.
End
;; Once we are out of the second while loop, we can copy the innermost parentheses...
;; contents to another location in RAM, and zero terminate it, or length pre-pend it.
;; then we delete the contents of that paren from the source string. doing so eliminates that...
;; ), so that the first while loop returns the position of the next ) in its test, so we loop until parens...
;; are all gone.
End
bump on that.
When i talk to people about order of operations...they say "make a tree". but my question is...how the heck do you make a "tree" in assembly? you just have arrays of bytes...
-
See this: http://www.dreamincode.net/forums/topic/286193-how-do-calculators-know-the-order-of-operations/ (http://www.dreamincode.net/forums/topic/286193-how-do-calculators-know-the-order-of-operations/)
You to do this you could have a function that calls itself. So here is example 3 + 3 * 4
+
/ \
3 * = 15
/ \
3 4
To evaluate this the function would look for the first operator it can find which is a "+" then the function would divide the expression into two expressions: [size=78%]"3" and also "3 * 4"[/size]
Then the function would call itself for each of the two functions to evaluate and add the value from each function because the operator is a plus.
so something like this
sub(evaluate,"3") + sub(evaluate,"3*4")
when running sub(evaluate,"3") the parser won't find any operator (of course) so it then knows that it is just a number and it just returns the number.
when running sub(evaluate, "3*4") ..... and so on so forth until it has the answer. You will need to add parentheses. Also it is very important to note that there are some problems with the method I showed. Think about what would happen if you evaluated "3 * 4 + 3" the program would return "21" but the answer is clearly "15". This could be solved by having the function also look for the next operator and acting appropriately.
I hope that this helps. :)
-
Ok, that helps a bit. So as a follow up to that... is Axe advanced enough now to take arbitrary Label names? Like you said sub(evaluate, [arg]). Can I do LBL EVALUATE? Or must I use the 2-character label names?
-
You can perfectly use Lbl EVALUATE. Axe allows up to 13 characters name, and you can also use lowercase.
(like Lbl Evaluate)
-
Nice! Didn't know that. Haven't been up to date on Axe's features before now. :p Is that the same for variable names now? Anything else it can do? lol
-
Nice! Didn't know that. Haven't been up to date on Axe's features before now. :p Is that the same for variable names now?
Yeah, you just need to "declare" them. For example do "L5->°MyVar", and then yo are able to do "Myvar++" and everything you want.
Anything else it can do?
Well just ask what you want it to do so we can answer that it is possible ;)
Basically, except maybe ultra advanced things such as patching the OS, you can do everything.
-
Thats pretty awesome. So it seems to me like Axe is being designed to at least *feel* like using a C-style language for the computer. Am I right?
As for functions, how about direct ROM call injection? Like using b_call(_MD5Init) or something, that require certain registers as input? Or if its not implemented, maybe a variation on sub(, where argument one is the ROM call name, and the other arguments are like loads into registers, in {PTR}->[register] format?
Edit: So here would be an all-text algorithm..
Lbl Evaluate
1. if number of ( > number of ); then error one or more paren not closed
2. if number of ( < number of ); then error, too many )
3. find innermost (...), dump expression into scrap RAM
4. repeat 3 for each wrapping (...), until there are no parentheses left to evaluate. Each iteration of this becomes an "entry" in scrap RAM. When we have no more parentheses, we dump the rest of the expression into scrap RAM.
5. For each entry in scrap RAM, break apart entry into expressions, by the operator, and perform * and / before + and -.
Would that work?
-
I feel like Xeda has probably done something like this before, maybe you can try bringing her here.
My first thought would be to break the expression down, convert all numbers into something you can read easily (ie from one byte per digit into BSD or just standard 2-byte (or more) numbers), then look for the first ')' (you could use cpir), follow that back to the '(' and evaluate that expression. Then shift the whole expression left so that the previous () is overwritten with a number. Repeat until no parentheses left. So "10,+,5,*,(,1,/,(,4,*,8,+,1,),),+,4" would first turn into "10,+,5,*,(,1,/,33,),+,4", then "10,+,5,*,.030303,+,4" then finally "14.151515".
-
Ok, ill talk to Xeda then. But, for now, let's talk algorithm.
step 1: error codes. Count up # of ( and # of ). If ( > ), then too many (, or if ( < ), then too many )
step 2: find first ). move backwards to first ( we find. That's the first thing to evaluate. Move expression contained to some other area, rinse and repeat until there are no more () sets.
step 3: dump whatever is left into some other area
step 4: parse some other area, with * and / first.
how difficult would it be to add support for other variables. like a,b,c,y,z and so on.
-
Support for other variables is just find and replace. You would probably do that when you parse the numbers to convert them into whatever format you plan on using, just replace the variable with the value it holds.
Step 2 and 4 will use the same code to parse, since there won't be any parentheses to evaluate in step 2 (you've found the innermost parenthesis), so you should just need one last call to the parse routine (that handles the multiplication, division, etc.). I think step 3 is unnecessary.
EDIT: Also, there are more possible errors than just the parentheses, for example you need to make sure there is a number/expression before and after every operator (2+3* is invalid, as is +2+3*4) and ideally you'd have something in between the parentheses (not "2+3*( )" ), but i would set that aside for now. I wrote a little parsing routine last night just to see how difficult this project would be, currently it just converts the numbers into a 2-byte number (that fits inside hl/de/bc/etc.) and finds the first parenthesis.
-
For the other variables, I'm talking about something to this effect:
3x+7y=-2x-14y
the calculator sees the =, and then the presence of x AND y, and automatically determines its a system of equations problem and solves for x and y.
As for the second part, if you're evaluating step 2 in my algorithm, you should still have () in there, or you should be on to step 3?
response to edit: yeah, those are also invalid. let's get the algorithm working, then we can work with error finding :p
-
I'm just saying that once you're at step 3, you should have a simplified equation, so all you need to do is pass that last equation back to your routine for evaluating expressions once more. You can just overwrite the space you're working with (it should be smaller anyway), there's no need to copy it someplace else, evaluate that, then copy it back. Just evaluate what you have there the same as you did for all the parenthesis pairs, just like treating it as if there were one final set of parentheses around the equation: ( 2+4*(3/(7+1))+3 ).
-
Ok, so my final question, for now, is this: this program is designed to simplify polynomial expressions. so for example, simplifying this: (x-1)(x+1) should result in x^2-1. How much more complicated is make it involve the x as an entity?
Also, when Axe command lists say a command takes EXPR as an argument, what does that mean exactly? What's the difference between EXPR and an Axe list, or an array of bytes?
-
Also, when Axe command lists say a command takes EXPR as an argument, what does that mean exactly? What's the difference between EXPR and an Axe list, or an array of bytes?
In the command list, EXP signifies any expression that returns a numerical result.
-
I'm not sure, if that's how you're planning on doing it, you might want to reconsider your algorithm. I'm not sure what the best way to do that might be, maybe working one "group" at a time? For example "3+x(2x-3(1+x))-3x(x^2+2)+2x", you would first work "x(2x-3(1+x))" then "3x(x^2+2)" and finally you'd put it all together and try to simplify it.
That seems a good deal more complicated, i'm not really sure how i'd go about it.
-
Deep Thought gave me another way to do it, which I'll modify slightly.
Create a stack, with number (or var), operator, and precedence,
where precedence is OpPrec + ( 2 * N).
OpPrec = 0 for addition or subtraction, 1 for multiplication and division
N = nesting level; every time we hit a (, we add 1 to N. Every time we hit a ), we minus 1 from N
Imagine the following: 7x + 3x^2 - (x^2 + (2x - 1))
7 is pushed as the the number
implicit multiplication, so * pushed
precedence = 1 + (2*0)
x is pushed as number
+ pushed
precedence 0
... and so on until...
hit the first (. Add 1 to N. N=1
x^2 is the value
operator is +
precedence is 0 + (2*1) = 2
hit next (. Add 1 to N. N=2
2 is the value
implicit multiplication.
precedence is 1 + (2 * 2) = 5
... and so on
Then, you take that stack, and process it in order of descending precedence.
-
Wait, DT is still around ? O.O
-
clrhome.org. He owns. Im one of the admins. I have ways to get a hold of him lol.
-
Oh LOL yeah forgot about that.
-
That sounds pretty much like what we were talking about before, only the other way didn't require a special stack as it's processed on the fly. That sounds like a fine method to me, personally i would start working on converting something like "3+2(4-1)" into "3 + 2*4 + 2*-1". Once you get to that point, adding X shouldn't be too difficult.