Norman Dunbar wrote:
Morning George,I wrote an expression evaluator once, many years ago, in SuperBasic and then converted it to C. Yeuch - all that recursion. I suspect the obvious answer to how the EE should be written is 'so that it conforms to arithmetic priority' as in brackets, multiplication/division addition/subtraction etc. There was an ancronym thingy we used to use at school, but that was many many years ago and I'm losing my mind, so I can't remember.
The one I was taught was BODMAS:
Brackets ()
Of x percent OF y
Divide /
Multiply *
Add +
Subtract -
However, this is slightly wrong if strictly adhered to: Multiply and Divide, and Add and Subtract are complementary, share equal priority and are normally calculated left to right. So what about:
5 - 2 + 3
as both - and + share equal priority, run left to right and get:
(5 - 2) + 3 -> 6
using strict BODMAS, Add comes before Subtract and get:
5 - (2 + 3) -> 0
However, if Subtract is thought of as Add negative, then we have:
5 - 2 + 3 => 5 + (-2) + 3 -> 6
The expression calculator I wrote assigned priorities to the operators and, worked left to right; if the next operator had a higher priority than the current operator, stack upto the previous operator and start the calulation from the previous operand with this operator. When an operation was done, the stacked up operator [priority] was checked against the next operator's priority. [Initially the calculation stated with the lowest priority pseudo operator.]
I based my priorities on C's priorities, but with one major difference: bitwise operators (&, etc) were the highest priority whereas logical operators (&&, etc) were where C had them - bitwise are most probably going to be bit masks and so should affect the nearest operand, not the nearest expression (as logicals, and C, do).
I wouldn't recommend my sources as they also handle variable and function extraction using a slightly odd syntax...though I may also have a DATA/BASIC version of an expression calculator around here somewhere I could possibly offer - that used pseudo recursion if I remember: it just stacked up the evaluated line without actually calling a function recursively.
