/*
The most flexible approach I can think of is the language Prolog, where new
operators can be defined by programs - e.g. in a Prolog program you can
extend the language by defining new operators e.g. 'blah' or '=>>>", while
in say C++ you have to stick to re-defining the existing operators.
In any language expressions can be though of as trees
infix op prefix op postfix op
/ \ \ /
exp1 exp2 exp exp
or at the lowest level, very simple terminal one-node trees e.g.
identifier (e.g. x, y, i, val), or literal ( 1, 1.0, 1E-4, "Fred"), or
function call ( func( exp1,..., expn) )
First define fixity or associativity of your ops... */
enum fixity {
fx, /* prefix operator f where (operated on) where x stands for an
expression of lower precedence*/
fy, /* prefix operator f where y stands for an expression of equal or
lower precedence
e.g. f=unary - f=or unary + parsed as +(+(-exp)) */
xfx, /*infix operator f where precedence of left & right expression is
lower precedence
e.g. >,>,>=,<= i.e. exp > exp > exp is illegal
xfy, /* right associative infix op f, a f (b f c) */
yfx, /* left associative infix ops e.g f=- and (a-b)-c */
/*there are no yfy operators because these would be ambiguous*/
xf, /*postfix op f on argument of lower precedence*/
yf /*postfix op f on argument of equal or lower precedence*/
}
/*
The pecedence of a terminal symbol (literal constant or an identifier or a
function call) is zero.
The precedence of an expression is the precedence of the operator "at the
top of the expession tree"
*/
struct op_def {
char *op; /* e.g. "+", "-", */
int precedence;
enum fixity; /* e.g. fx, fy, xfx, xfy, yfx, xf, yf*/
};
/*
then get your recursive greedy parser to generate expression trees and carry
around the highest precedence of an expression it is willing to accept in
the current context - if it has finished parsing an expression and it sees
the
next symbol is an op then look at the op table for the fixity and precedence
of the op at the top of the tree you have just parsed and the op that is
next in the input stream and decide whether to return of continue, and if
you continue decide which op goes at the top of the new tree
*/
"gamehack" <ga******@gmail.com> wrote in message
news:11*********************@g43g2000cwa.googlegro ups.com...
Hi all,
I was thinking about parsing equations but I can't think of any generic
approach. Basically I have a struct called math_term which is something
like:
struct math_term {
char sign;
int constant;
int x;
int y;
int xpower;
int ypower;
}
For example say the user inputs this:
6x^2-8x^3+5
Then this would be transformed to 3 structs
6x^2: sign = '+'; constant = 6; x = 1; y = 0; xpower = 2; ypower = 0;
-8x^3: sign = '-'; constant = 8; x = 1; y = 0; xpower = 3; ypower = 0;
+5: sign = '+'; constant = 5; x = 0; y = 0; xpower = 0; ypower = 0;
My problem is getting the input into my structured form. Also I was
thinking of implementing brackets but I wasn't sure what datastructure
to use to hold all the terms. A linked list probably? Or a bin tree? I
wasn't able to figure out how to handle the case
(6x^2 + 3x)/(9x^3)
Any pointers on how to proceed from here are greatly appreciated. I
just need the general idea how to go about the problem and I'll figure
out how to implement it. Thanks