Jump to content

[MATHS]: Recursive Descent or Shunting Yard


Recommended Posts

Dear CnCNet-Forums,


I've been looking to develop a math-parser since a looong time but have never got around to actually do it.


So the difficulty is to actually parse mathematical expressions into terms/operators/functions so as to be able to analyze and solve them later.


As far as I'm aware there's 4 ways to do it:



So, I'm actually leaning towards rolling a recursive descent parser by hand as I believe it to be the best, most extensible, generic and customizable solution although it would probably be the most work of all of these.


Basically, I've had discussions with Frank "zzattack" Razenberg about it and he suggests using the shunting-yard approach as we both agree that it would most likely be the fastest/easiest to do as it's specialized for mathematical expressions, although I am not sure how well this would work with really complex expressions that include many variables or even vector math. Frank seems to think that it wouldn't be a problem but I'm not so sure about this.


I didn't even think about abusing RegEx to do it, but that's what Frank told me he used before to make a differential calculator.  :P


Has anyone ever done anything similar in the past and can contribute?!  :P







Link to comment
Share on other sites

Well, I finally decided to use the Shunting Yard approach and after writing 400 lines today I got a fully fledged expression parser and evaluator.



The problem which I'm facing now: I don't know how to deal with unary minuses. When I'm evaluating an expression I have no way of knowing whether the minus is unary or binary because RPN doesn't account for it.  :puppydog:


I figured that 1 way to deal with it would be just prefixing every unary minus with a 0.


So -hack() becomes 0 - hack(), which would work.


But in the case of x / -hack() I cannot just prepend a 0 because that would become x / 0 - hack().



Does anyone have any idea how to go about this? Is there even any way to use unary operators in RPN?

I read that I could invent one myself, which I guess is what I'm going to do next.  :roll:






Link to comment
Share on other sites

"Solved" it already. Added detection for unary operators.


// first handle unary operators (preceeded by another operator, a parenthesis or first token of the input)
token_type prev = prev_tok.type;
if (prev == token_type::op || prev == token_type::paren_left || prev == token_type::none) {
if (tok.lexeme.front() == '-') {
	// mark unary minus
	tok.lexeme = "#";
if (tok.lexeme.front() == '+') {
	// ignore any unary plus





Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Recently Browsing   0 members

    • No registered users viewing this page.
  • Create New...