Now that the summer is over, I can direct my attention back to two calculator projects I've put off...Legend of Zelda, and Polynomials All-in-One, the remake. So, as of the last I looked at my notes, I have a basic algorithm that accounts for nested parentheses. So, to remind anyone viewing this, take this example:

3x^2 - (7x + 2) / (3x - 1)

The OOP assigns operator precedence by the following formula:

P = 2(N) + L
where L = 0 for + or - and 1 for * or /
and N = # of nested parentheses

So the first term is 3x^2. The first operator precedence is 2(0) + 0 = 0
The second term is 7x. The operator precedence is 2(1) + 0 = 2
The third term is 2. The operator precedence is 2(0) + 1 = 1
The fourth term is 3x. The operator precedence is 2(1) + 0 = 2
The final term is 1. The operator precedence is 2(1) + 0 = 2.
(This may need some pruning)

But, the problem with an algorithm of this style is that in places like the division above, the algorithm falls apart. Can anyone think of a workaround, or perhaps a better way to do this?

bump

Use an actual parser rather than ad-hoc heuristics.

For example, read the answer Tari already wrote you about this a few months ago rather than ignore it.

Tari's answer factored into my algorithm, but perhaps there's a part of it I'm missing since I don't see how it can handle operations with 2 multi-term polynomials...wouldnt it just do them one by one in a wrong order, causing a wrong answer? Perhaps the route to take here tho is to ask Tari directly. I'll shoot a PM to Tari.

Update:

PM'd Tari and after thinking about the response, decided to do this.
Take 3x + (7x-1)/(4x+2) as one example and 3x + (7x-1)/4x + 2 as another.

Ex1: 3x + (7x+1)/(4x+2)
*Every time the parser hits a () pair, whatever is inside is declared a Group
1. The final output starts as an array, filled to 0.
2. First, we add 7x+1 to the stack, then we add 4x+2 to the stack. That's group 1 and 2.
3. First, we pass 3x, with a + to the stack (since its first, it has no operation before it, it just w/e you see, so we can give it a +.

So, by the end of step 4, the stack looks like

: 7x + 1 _
: 4x + 2 /
: 3x +

So, when you process the stack, its (7x + 1) / (4x + 2), then that + 3x.

Now, that works for all instances like that. But, what happens when you have something like 7x - .... Subtracting 3x from the result isn't the same. So, maybe to solve that issue, have a bit or something to indicate whether the argument we're working with next is the first or second operand.

http://en.wikipedia.org/wiki/Shunting-yard_algorithm

How do the +, -, *, and / tokens show up in Axe, as data? The last time i made this program, when i typed in 7x+7, the output was 7xp7.

This post has been edited. Scroll down.

Ok, so I've come up with something after speaking with Tari, Xeda, and reading the shunting yard stuff.

Here's an example equation:

3x + 7x^2 - (3 - (7x + 1))

This is what gets done. Stack based.

E1: 3x, 7x^2, +
E2: _, g1, - ( the _ denotes whether the term added is the first or second operand, so we process it right. In this example, its the result of E1 that is supplied as operand 1 and E2 is operand 2.)

Then somewhere else:
G1: 3, g2, -
G2: 7x, 1, +

First, we process the groups in descending order, then we take the stack and order it by precedence. Each stack entry can have a size word so we know where to look for the operator precedence. Once we do that, its just a matter of processing the stack in order and we should be good. Pseudo-coding this now.

Edit::

This algorithm falls apart when operations beyond + and - are used. So I revised it a bit. Instead, everything from one + or - to the next or from beginning to a + or - or from one to the end is a group.

3x^2 - 7x/(3x+1)4x

Step 1: convert -'s
3x^2 + (-7x)/(3x+1)4x
Step 2: convert to group notation
G1 + G2
Step 3: define groups and nest additional groups if needed
G1: 3x^2
G2: -7x/(3x+1)4x
Step 4: process groups in descending order, then plug into final equation.

bump

What grammar are you actually trying to parse? Don't bother trying to implement something unless you can answer that question, because trying to solve problems that you don't understand will just lead to a lot of frustration.


This:

Code:

will get you variables for each letter, floating point and integers, plus a grammar that is really very nearly an operator-precedence grammar (and can be converted into one if written in a slightly messier format). Unfortunately, a true operator-precedence grammar doesn't allow adjacent nonterminals, which in this grammar appears to be required for reasonable support for implicit multiplication - notice that it's possible for an exp_expr and some paren_expr's to neighbor one another, without a NUM or ID intervening. However, you can trivially convert it into a proper operator precedence grammar by substituting thes rule for paren_expr and exp_expr upwards into the implicit_mul rule, the '(' and ')' terminals magically appear to do their separating work, so we needn't worry about being able to construct the precedence table, and leave it in this format for clarity.

The only rule that's even a little complicated here is the implicit_mul rule - which is tailored to prevent different numbers from getting smushed together multiplicatively (e.g. you don't want to think that that 25 is really 2*5 or vice versa, nor that 2*5^2 is 25^2 or vice versa).

From here you can trivially assign operator precedences (and associativity directions), and just implement textbook shunting yard.

Well, what I was trying to do was to process the expression by term, to save the processing time associated with breaking something like 3x^2 into 3*x^2 and having to basically do 2 steps. I figured I could handle what's inside the terms later. But after speaking with Deep Thought a bit, I've realized that I'd have to break up the term eventually anyway, and that the parser should be able to handle more variables than just x, and that if you spend more time trying to parse the expression at first, it makes doing the mathematical stuff later easier and quicker.