[MATHS]: Recursive Descent or Shunting Yard

[SiRaLeX]

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:

 

• Using Dijkstras shunting-yard algorithm
  
• Writing a recursive descent parser by hand
  
• Using a parser generator like Boost.Spirit
  
• Using RegEx (I believe this would be the worst option although it could work)
  

 

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. 

 

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

 

Greetings,

SiRaLeX

 

 

 

[Iran]

Are you gonna use this to write more gay cheats

[SiRaLeX]

Are you gonna use this to write more gay cheats

 

Yes. Can you help me? 

 

 

[SiRaLeX]

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:

 

 

 

 

 

[SiRaLeX]

"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
	continue;
}
}