Re: string parsing algorithm


"Thomas Kreuzer" <thomas.kreuzer@xxxxxxxxxxxxxx> wrote:

Hello everyone,

I have a question regarding string parsing for arithmetic expressions
like (1+5)*7-6/3
The problem, of course, being the priorities of the arithmetic operations.
Most compilers etc must have a string parser like this, and I am
currently trying to code one myself but don't have a clue what might be
most effective way of doing it.

First I thought about making it recursively, like search for the first
operator with the least priority, split the string and so on.
Or I thought about putting the numbers in a list and the operators in a
different list, and then perform the operations based on their index,
e.g. index of "*" in the operator list and use that index and index+1
for the operand list etc.

I am sure there are better algorithms I didn't come up with, so can
anyone point me to a direction of algorithm to use?
Source files, or just general ideas, everything would be helpful.

I wrote a calculator in C a while back that takes an expression like:

(36-4.2+17)*(86.3/42.7)+94.3

and calculates and prints its value.

It involved basically this plan:

Split the expression in two, delimited by the left-most LOWEST-precedence
zeroeth-parenthetical-level operator. Feed the two halves recursively
back into the parser, and feed the return values into the function
associated with the current operator.

Thus, the calculation is turned into an upside-down tree, with the
left-most lowest-precedence zeroeth-level operator as the top node.
The highest-precedence operators are parsed last.

At the bottom of the tree, when all the parsing is done, the actual
calculating begins, starting with the highest-precedence operators, and
continuing upward through the tree, with the lowest-precedence operators
being calculated last when we get back to the top of the tree.

Does that sound confusing? Don't feel bad. It *IS* confusing. It took
me a long while to figure out how to do that. I basically had to teach
my computer to think in the same way an algebra student thinks: by
pushing lower-precedence operations onto a mental "stack" to be done later,
doing the higher-precedence operations, then popping the lower-precedence
operations off the stack and doing those last.

(I could chicken out and say something pretentious like "make a grammar
and use a stack of recursive decent parsers", but if you already know
what that gobbledygook means, then you wouldn't have asked the question
you asked; so I did my best to put it in plain English. My apologies
if I've failed to make it "plain".)

(No offense to the persons who suggest "grammars" and "recursive decent
parsers" elsewhere in this thread; that's sound advice, but I decided
to also include the "recursive decent for dummies" version.)

I think I'll post the C code for my calculator this evening when I get
home, so you can see what I'm talking about.


--
Cheers,
Robbie Hatley
Tustin, CA, USA
lone wolf intj at pac bell dot net
(put "[usenet]" in subject to bypass spam filter)
home dot pac bell dot net slant earnur slant


.

Relevant Pages

  • Re: Whole Nos!
    ... The calculator also has a Inverse ... Dim OffVal As Variant, IntBit As Variant ... Dim TempVal As String ... value (the text box is just for display) then you may simply circumvent these problems entirely. ...
    (microsoft.public.vb.general.discussion)
  • Re: Why do people need to back up their memory on a SD card?
    ... onto a SD card? ... Do you have Microsoft Word in your calculator? ... In the case of "string" objects, ... Cable transfer software includes a "text" transfer mode which already ...
    (comp.sys.hp48)
  • Re: 0 SIZE returns 0.; bug?
    ... Apparently the calculator ... taking an entire received file (string) as input. ... invalid binary transfers as character string objects, ... anything else if the binary transfer header is correct. ...
    (comp.sys.hp48)
  • Re: built-in file copy chews my files
    ... i can see that this doesn't actually benefit the calculator system directly ... You evidently mean, when you copy *computer* files to the SD card, ... an arbitrary computer file is stored in the calculator ... The string is the exact image, bit for bit, of the computer file, ...
    (comp.sys.hp48)
Loading