I'm not sure whether someone else has commented on this. I am yet to read the comments. Maybe I will read them soon enough.
Anyways and however, speaking in strict mathetical sense, the model of a tree actually breaks the classical mathematical model of operator precedence.
1 + 1 + 1 evaluates to:
(+)
/ \
(+) (1)
/ \
(1) (1)
The above will be correct, mathematically, but will break once you involve multiple mathematical operators in the statement. Because, mathematically, operators have precedence.
The operators are essentially ordered based on their depth into the right of the question / statement but unless I am terribly wrong, this is not the case in mathematics and some operators have higher precedence regardless of their position in the statement.
Next operation is (+), this one floats, and as it's the same weight at the root it doesn't matter its relationship with it, so we put it higher.
Turns you have a fairly, if not a very complicated tree for a simple problem. But, fair, enough, you can always get AI to write the code for this and probably, the code will be reused over and over.
But, is it just me or does someone else think that having to rebalance or re-order the tree might be a good breaking point for the camels back?
If you want to have the full operation recorded this is the way to do it. Either this or a non-binary tree in where multiple operators with the same operand and level are all together:
If you transform the mathematical operation to lisp terms you will have the tree explicitly written.
The only way that I can think of to make it simpler is to go the array language route of going right to left and ignore precedence, or some similar way of working.
The code to create the tree should not complex, so yes, AI could be used, but most competent coders should be able to create a basic version and test it in an afternoon.
If you are parsing left to right it can be quite easy to balance things, you should not need rebalancing at all. When you are in an operation node and you have to add an operation of the same level of priority, you always get the existing operation and subtree, put it on the left of the new operation, and continue from there.
With this if you try to do - next to a - or +, or a / to a / or *, you'll be preserving the order of the operations, and the calculation will be correct. Try it with 2*3/4.
>The code to create the tree should not complex, so yes, AI could be used, but most competent coders should be able to create a basic version and test it in an afternoon.
I generally tend to find the idea of 'competent' coders misleading. For the most part, I have been developing or writing code in a certain language for while, then it turns out that I am competent coder? Because, yeah, I've been using C or Python for a while and can easily solve a lot of "complex" problems in C but with all due respect, I am obviously not a competent coder. It's like a situation where you frequent a certain part of town that you're very familiar with it and the people living there but then at the same time you don't live there - lol.
Anyways, for this problem I would parse this statement but definitely not into a tree. I'd assign the integrals to objects. I would then parse or go through the statement again executing the operands.
I'm not saying that competent coders will see the problem and think about doing trees and code it that way. I'm saying that if you have that problem and want to solve it with trees (so knowing the problem and a solution) they should be able to program it.
And in a way you are solving it the same way, if I understood you correctly.
Assuming you mean that you'd have classes, and create objects with the operations, it's the same as a tree.
1+2*3^(4+1)+2/3 -> plus( plus(1, mul(2, power(3, plus(4,1)))), div (2/3)) would be the object hierarchy created.
OTOH if you are parsing it and doing the operations that can be done because all the operands are known:
You'd be, once again, doing the tree but instead of having it as an structure you'd be directly parsing the leafs than can be operated and act on them. This way would maybe be faster for simpler expressions (no need to construct the tree), but probably be more expensive than tree construction and resolution for more complex ones.
ReDress · · focus · HN ↗
Anyways and however, speaking in strict mathetical sense, the model of a tree actually breaks the classical mathematical model of operator precedence.
1 + 1 + 1 evaluates to:
The above will be correct, mathematically, but will break once you involve multiple mathematical operators in the statement. Because, mathematically, operators have precedence.The operators are essentially ordered based on their depth into the right of the question / statement but unless I am terribly wrong, this is not the case in mathematics and some operators have higher precedence regardless of their position in the statement.
Any comments on this?
JaumeGreen · · focus · HN ↗
1+2*3^(4+1)+2/3
We start the evaluation with 1+, the chain would be on (+) for now.
The next operator is (*), and because this one is heavier it falls down, bringing 2 with it. Now checking the next operator (^), once again heavier, goes down the three. The next operation is between parenthesis, that takes precedence and goes down, but the pointer comes up after the operation has taken place. Next operation is (+), this one floats, and as it's the same weight at the root it doesn't matter its relationship with it, so we put it higher. Finally we got the division, which is heavier again. Did this on the fly, so it might have edge cases, but it works well as a starting point.ReDress · · focus · HN ↗
Turns you have a fairly, if not a very complicated tree for a simple problem. But, fair, enough, you can always get AI to write the code for this and probably, the code will be reused over and over.
But, is it just me or does someone else think that having to rebalance or re-order the tree might be a good breaking point for the camels back?
:-)
JaumeGreen · · focus · HN ↗
The only way that I can think of to make it simpler is to go the array language route of going right to left and ignore precedence, or some similar way of working.
The code to create the tree should not complex, so yes, AI could be used, but most competent coders should be able to create a basic version and test it in an afternoon.
If you are parsing left to right it can be quite easy to balance things, you should not need rebalancing at all. When you are in an operation node and you have to add an operation of the same level of priority, you always get the existing operation and subtree, put it on the left of the new operation, and continue from there.
With this if you try to do - next to a - or +, or a / to a / or *, you'll be preserving the order of the operations, and the calculation will be correct. Try it with 2*3/4.
If you add some more operations to the right (*2/5*12/7) you keep growing the tree. It will not be balanced, but it doesn't need to be.ReDress · · focus · HN ↗
I generally tend to find the idea of 'competent' coders misleading. For the most part, I have been developing or writing code in a certain language for while, then it turns out that I am competent coder? Because, yeah, I've been using C or Python for a while and can easily solve a lot of "complex" problems in C but with all due respect, I am obviously not a competent coder. It's like a situation where you frequent a certain part of town that you're very familiar with it and the people living there but then at the same time you don't live there - lol.
Anyways, for this problem I would parse this statement but definitely not into a tree. I'd assign the integrals to objects. I would then parse or go through the statement again executing the operands.
Well...
JaumeGreen · · focus · HN ↗
And in a way you are solving it the same way, if I understood you correctly.
Assuming you mean that you'd have classes, and create objects with the operations, it's the same as a tree.
1+2*3^(4+1)+2/3 -> plus( plus(1, mul(2, power(3, plus(4,1)))), div (2/3)) would be the object hierarchy created.
OTOH if you are parsing it and doing the operations that can be done because all the operands are known:
1+2*3^(4+1)+2/3 -> 1+2*3^5+0.66 -> 1+2*243+0.66 -> 1+486+0.66 -> 487.66
You'd be, once again, doing the tree but instead of having it as an structure you'd be directly parsing the leafs than can be operated and act on them. This way would maybe be faster for simpler expressions (no need to construct the tree), but probably be more expensive than tree construction and resolution for more complex ones.