> I am looking for an algorithm to do mathematical processing. So given a
> string of 2 * 3 + 1 would produce 7 as an answer. I seem to recall the
> easiest way is to do this with a stack, but instead of trying to figure it
> out again I decided to go RAD and ask for some help. Any takers??
Left recursive parsing... I'm not going to give a comlpete solution...
Number * Number + Number
becomes
Add(Multiply(Number,Number),Number);
Basicly you take your string and pull characters off until you get a valid token
Tokens would be Numbers, + and *.
Something like
type
TTokenType = (ttERROR,ttEOS,ttNUMEBR,ttMULT,ttADD);
RToken = record
TokenType :TTokenType;
S :String;
end;
function GetToken(var S :String):RToken;
var
I :Integer;
begin
// get the first token off the string (in this simple case a cascaded case
statement and for
// loop is sufficient)
// Return the token retrieved and assign the remainder of the string to S
// Simple case where Numbers are exactly 1 character long
if S='' then begin
Result.TokenType := ttEOS;
end
else begin
Result.S := S[1];
case S[1] of
'0'..'9':Result.TokenType := ttNUMBER;
'+': Result.TokenType := ttADD;
'*': Result.TokenType := ttMULT;
else Result.TokenType := ttERROR;
end;
S := copy(S,2,Length(S)-1);
end;
end;
now you can process left to right the tokens keeping an accumulator of the current
information gathered building up a parse-tree and then execute the parse-tree.
if you build your parse nodes with an execute function with result you can execute
the tree. If you're cunning you can support variables and enable assigning values to
the variables prior to execution.
For a simple calculator this is not a complex task. And you can even make this
extensible
(each parse-node type should derive from a base-class) through Function Identifiers and
parameter list support making a complete excel-like function evaluator.
I'd recommend getting some online info on Left Recursive Parsing, Lexical Analysis or
for more
powerful parsing look at shift-reduce parsing.
there should be a few expression parsers around since as I said the basic expressions
are
not too hard to deal with (Brackets are not an issue, they simply provide grouping,
you don't
have to treat them as a separate parse-node unless you really feel uncomfortable with
dissolving a portion of your expression...
I can discuss this furthur if you wish (on or off the list).
--
Aaron Scott-Boddendijk
Jump Productions
(07) 838-3371 Voice
(07) 838-3372 Fax
---------------------------------------------------------------------------
New Zealand Delphi Users group - Delphi List - [EMAIL PROTECTED]
Website: http://www.delphi.org.nz
