Author Topic: Order of Operations  (Read 6766 times)

0 Members and 1 Guest are viewing this topic.

Offline ACagliano

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 919
  • Rating: +32/-2
    • View Profile
    • ClrHome Productions
Order of Operations
« 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.

Offline Aspiring

  • LV3 Member (Next: 100)
  • ***
  • Posts: 81
  • Rating: +5/-0
  • The only source of knowledge is experience-Einsten
    • View Profile
Re: Order of Operations
« Reply #1 on: April 01, 2014, 04:27:37 pm »
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.)

Offline ACagliano

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 919
  • Rating: +32/-2
    • View Profile
    • ClrHome Productions
Re: Order of Operations
« Reply #2 on: April 01, 2014, 05:25:42 pm »
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...

Offline Hayleia

  • Programming Absol
  • Coder Of Tomorrow
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3367
  • Rating: +393/-7
    • View Profile
Re: Order of Operations
« Reply #3 on: April 01, 2014, 05:41:17 pm »
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.
I own: 83+ ; 84+SE ; 76.fr ; CX CAS ; Prizm ; 84+CSE
Sorry if I answer with something that seems unrelated, English is not my primary language and I might not have understood well. Sorry if I make English mistakes too.

click here to know where you got your last +1s

Offline Aspiring

  • LV3 Member (Next: 100)
  • ***
  • Posts: 81
  • Rating: +5/-0
  • The only source of knowledge is experience-Einsten
    • View Profile
Re: Order of Operations
« Reply #4 on: April 01, 2014, 07:30:04 pm »
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.

Offline ACagliano

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 919
  • Rating: +32/-2
    • View Profile
    • ClrHome Productions
Re: Order of Operations
« Reply #5 on: April 01, 2014, 09:50:37 pm »
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:



Code: [Select]
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
   

Offline ACagliano

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 919
  • Rating: +32/-2
    • View Profile
    • ClrHome Productions
Re: Order of Operations
« Reply #6 on: April 03, 2014, 08:16:33 am »
bumpity bump

Offline ACagliano

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 919
  • Rating: +32/-2
    • View Profile
    • ClrHome Productions
Re: Order of Operations
« Reply #7 on: April 04, 2014, 09:54:17 pm »
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:



Code: [Select]
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...

Offline Aspiring

  • LV3 Member (Next: 100)
  • ***
  • Posts: 81
  • Rating: +5/-0
  • The only source of knowledge is experience-Einsten
    • View Profile
Re: Order of Operations
« Reply #8 on: April 04, 2014, 10:30:45 pm »
See this: 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. :)

Offline ACagliano

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 919
  • Rating: +32/-2
    • View Profile
    • ClrHome Productions
Re: Order of Operations
« Reply #9 on: April 05, 2014, 10:23:25 am »
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?

Offline TheMachine02

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 452
  • Rating: +105/-0
  • me = EF99+F41A
    • View Profile
Re: Order of Operations
« Reply #10 on: April 05, 2014, 10:27:00 am »
You can perfectly use Lbl EVALUATE. Axe allows up to 13 characters name, and you can also use lowercase.
(like Lbl Evaluate)
AXE/asm programmer - unleash the power of z80 //C++//C

epic 3D things http://www.ntu.edu.sg/home/ehchua/programming/opengl/CG_BasicsTheory.html

Offline ACagliano

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 919
  • Rating: +32/-2
    • View Profile
    • ClrHome Productions
Re: Order of Operations
« Reply #11 on: April 05, 2014, 12:19:21 pm »
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

Offline Hayleia

  • Programming Absol
  • Coder Of Tomorrow
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3367
  • Rating: +393/-7
    • View Profile
Re: Order of Operations
« Reply #12 on: April 05, 2014, 12:31:45 pm »
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.
I own: 83+ ; 84+SE ; 76.fr ; CX CAS ; Prizm ; 84+CSE
Sorry if I answer with something that seems unrelated, English is not my primary language and I might not have understood well. Sorry if I make English mistakes too.

click here to know where you got your last +1s

Offline ACagliano

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 919
  • Rating: +32/-2
    • View Profile
    • ClrHome Productions
Re: Order of Operations
« Reply #13 on: April 05, 2014, 02:32:26 pm »
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?
« Last Edit: April 05, 2014, 03:16:41 pm by ACagliano »

Offline chickendude

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 817
  • Rating: +90/-1
  • Pro-Riot Squad
    • View Profile
Re: Order of Operations
« Reply #14 on: April 05, 2014, 11:05:48 pm »
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".
« Last Edit: April 05, 2014, 11:07:42 pm by chickendude »