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 5 3258
On 2006-02-03, gamehack <ga******@gmail .com> wrote: 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
There's a specific kind of tree that's useful for this, and you'd
basically have a node that is either a number or an operator with
further nodes below it
(warning, beware the fixed-font ascii diagrams)
for 6x^2-8x^3+5 you'd have
+
.'.
- 5
.' .
* *
..'. .'.
6 ^ 8 ^
.'. .'.
x 2 x 3
For (6x^2+3x)/(9x^3), you'd get this
/
. ' .
+ *
. ' . .'.
* * 9 ^
..'. .'. .'.
6 ^ 3 x x 3
.'.
x 2
gamehack wrote: 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
Have a look at the "dragon book":
"Compilers, principles, techniques, and tools"
by Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman
(Addison-Wesley Pub. Co., 1986)
They discuss all the methods.
I personally employ recursive descent, using a stack that holds pointers
to the sub-expressions and operators. Others prefer a tree structure. Yet
others like the "operator precedence grammar". There is a notation called
Backus-Naur Format (BNF) for expressing how parsers work. It is described
in the dragon book. A mini-Fortran parser I wrote uses these rules:
----------------------------- Backus-Naur Rules for mini FORTRAN
NOTATION:
| -> "or",
+ -> "unlimited repetitions"
Q -> "empty set"
& -> + | -
% -> * | /
NUMBERS:
fp# -> {-|Q}{digit.digit + | .digit digit+} exponent
exponent -> {dDeE {&|Q} digit {digit|Q} {digit|Q} | Q}
FORMULAS:
assignment -> id = expression
id -> name | name {+ Forth }+ --curly braces balance!
name -> letter {letter|digit}+
arglist -> ( expression {,expression}+ )
function -> id arglist
expression -> term | expression & term
term -> factor | term % factor
factor -> id | fp# | ( expr ) | f^f | function
------------------------------------------ end Backus-Naur Rules
Consider an "expression ": the rules say it can be either a "term" or
a "term" joined to an "expression " (that is, a sub-expression) by a +
or - . This is a natural for recursion, since after finding a + or -
and peeling off the leading term the expression-parsing function can
then call itself using the pointers to the sub-expression (everything
to the right of the + or - ) as input.
Doing things in this order is "left-to-right" or LR parsing. There is
no rule that you couldn't do it from right to left.
But as I note, this is not the only way to proceed, and lots of people
prefer to do it other ways.
--
Julian V. Noble
Professor Emeritus of Physics http://galileo.phys.virginia.edu/~jvn/
"As democracy is perfected, the office of president represents, more and
more closely, the inner soul of the people. On some great and glorious
day the plain folks of the land will reach their heart's desire at last
and the White House will be adorned by a downright moron."
--- H. L. Mencken (1880 - 1956)
/*
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******** *************@g 43g2000cwa.goog legroups.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
Julian V. Noble wrote: gamehack wrote: 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
Have a look at the "dragon book":
"Compilers, principles, techniques, and tools" by Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman (Addison-Wesley Pub. Co., 1986)
They discuss all the methods.
I personally employ recursive descent, using a stack that holds pointers to the sub-expressions and operators. Others prefer a tree structure. Yet others like the "operator precedence grammar". There is a notation called Backus-Naur Format (BNF) for expressing how parsers work. It is described in the dragon book. A mini-Fortran parser I wrote uses these rules:
----------------------------- Backus-Naur Rules for mini FORTRAN NOTATION: | -> "or", + -> "unlimited repetitions" Q -> "empty set" & -> + | - % -> * | /
NUMBERS: fp# -> {-|Q}{digit.digit + | .digit digit+} exponent exponent -> {dDeE {&|Q} digit {digit|Q} {digit|Q} | Q}
FORMULAS: assignment -> id = expression id -> name | name {+ Forth }+ --curly braces balance! name -> letter {letter|digit}+ arglist -> ( expression {,expression}+ ) function -> id arglist expression -> term | expression & term term -> factor | term % factor factor -> id | fp# | ( expr ) | f^f | function ------------------------------------------ end Backus-Naur Rules
Consider an "expression ": the rules say it can be either a "term" or a "term" joined to an "expression " (that is, a sub-expression) by a + or - . This is a natural for recursion, since after finding a + or - and peeling off the leading term the expression-parsing function can then call itself using the pointers to the sub-expression (everything to the right of the + or - ) as input.
Doing things in this order is "left-to-right" or LR parsing. There is no rule that you couldn't do it from right to left.
But as I note, this is not the only way to proceed, and lots of people prefer to do it other ways.
-- Julian V. Noble Professor Emeritus of Physics
http://galileo.phys.virginia.edu/~jvn/
"As democracy is perfected, the office of president represents, more and more closely, the inner soul of the people. On some great and glorious day the plain folks of the land will reach their heart's desire at last and the White House will be adorned by a downright moron."
--- H. L. Mencken (1880 - 1956)
Do you have any online tutorials that explain how to do the parsing
with a stack and/or a tree? Thanks a lot
PS. I did google but couldn't find anything relevant
enum fixity; /* e.g. fx, fy, xfx, xfy, yfx, xf, yf*/
should have been
enum fixity fixity_of_op; /* e.g. fx, fy, xfx, xfy, yfx, xf, yf*/
"Paul Connolly" <pg********@blu eyonder.co.uk> wrote in message
news:dE******** *************@f e2.news.blueyon der.co.uk... /* 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******** *************@g 43g2000cwa.goog legroups.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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Sven Dzepina |
last post by:
Hello people =)
Has somebody a nice script, which can solve equations ?
It would be super, if someone has an idea where I can get such a script /
code in php.
Thanks.
Gretting!
|
by: Russell Blau |
last post by:
This is not really a Python question, but it does relate to a Python program
I'm working on, so this seems like as good a place as any to ask for
suggestions ...
I'm working on a GUI application that lets the user enter an alegbraic
equation and displays a nicely-formatted representation of the same equation
(and then maybe does other stuff with it). The question is: if you have an
equation containing terms such as x * y / z, which way...
|
by: Brian Kazian |
last post by:
Here's my problem, and hopefully someone can help me figure out if there is
a good way to do this.
I am writing a program that allows the user to enter an equation in a text
field using pre-existing variables. They then enter numerical values for
these variables, or can tell the program to randomize the values used within
a certain bounds. My problem is taking in this equation they have written
in the text field and converting it into...
|
by: Stud Muffin |
last post by:
Hey
Basically, I'm trying to take objects created in microsoft word using
equation editor (for creating clean looking math/physics equations)
and putting them into some sort of webpage format. But they come out
grossly unalligned and ugly when I try to directly copy and paste into
microsoft frontpage 2000. Few things I could do is place them directly
using x/y coord (which i don't know how to do), or just taking
screenshots and use...
|
by: w33nie |
last post by:
My table is pretty well complete, but I would prefer it if the value for Points could be turned into a mathematical equation,
and this equation would use the data from the other fields in the table to achieve a value.
I want this done in phpMyAdmin 2.7, if possible, so that when I change the values in other fields, the Points variable changes, due to its equation.
The equation I would want would be something like:
"won * 3 + drawn * 1"...
| |
by: Trev17 |
last post by:
Hello, I am new to C++ and i have tried for several hours to make a program my teacher has given me as a lab. Here is the Lab question:
the roots of the quadratic equation ax^2 + bx + c = 0, a cannot equal 0 are given by the following formula -b + or - square root of (b^2 - 4ac) / 2a.
If b^2 - 4ac = 0 then equation has a single root. if b^2 - 4ac > 0 then equation has two real roots. if b^2 - 4ac < 0 then equation has two complex...
|
by: trashman.horlicks |
last post by:
Hi,
A few months ago, I saw an equation parser, written in c#, and using
regular expressions (I think!), but now I cannot recall where I saw
it- if anyone saw anything like this, could they please post the url?
the parser not only dealt with operator precedence, but also the use
of brackets, so that any complicated expession could be re-written as
an equation that could be read from left-to-right, as a simple
sequence of sub-equations...
|
by: Constantine AI |
last post by:
Hi i am having a little problem with an equation function that was created from all your help previously. The function works fine itself but with a small glitch within it.
Here is the function code.
Public Function fCalcEquation(strEquation As String) As Long
Dim MyDB As DAO.Database
Dim rstParameters As DAO.Recordset
Dim intParamPosition As Integer
Dim strParameter As String
Dim strValue As String
|
by: phoenix1990 |
last post by:
so i have an entry frame where i want to input an equation, and i need to turn the string into an actual equation in terms of x. so that i can plot it on a canvas.
i already know how to make the entry frame, and how to extract the string equation that was inputed.
the only problem i'm having is converting it into an actual equation.
e.g.
the string input is 'sin(x)'
and i want to turn it into sin(x)
x is defined by another entry frame...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
| |
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |