C++ infix to postfix conversion for logical conditions

Question

I want to evaluate one expression in C++. To evaluate it, I want the expression to be converted to prefix format.

Here is an example

 wstring expression = "Feature1 And Feature2";

Here are possible ways.

 expression = "Feature1 And (Feature2 Or Feature3)";

 expression = "Not Feature1 Or Feature3";

Here And, Or, Not are reserved words and parentheses ("(", )) are used for scope

Not has higher precedence

And is set next precedence to Not

Or is set to next precedence to And

WHITE SPACE used for delimiter. Expression has no other elements like TAB, NEWLINE

I don't need arithmetic expressions. I can do the evaluation but can somebody help me to convert the strings to prefix notation?

Answer 1

Use a parser generator like the Lex/Yacc pair.

Answer 2

You will need to construct the grammar up front. So why do all the parsing by hand. Instead use a parser builder library like Boost-Spirit. Or lex/yacc or flex/bison.

Then use the AST generated by the parser builder to output the data in any way you see fit. Such as infix to prefix or postfix, ...etc.

Answer 3

I guess your intention is to evaluate condition. hence you dont need a full fledged parser.

First of all you dont need to work with strings here. 1. Convert "Feature 1" to say an Id (An integer which represents a feature)

So, the statement "Feature1 And (Feature2 Or Feature3)"; to say (1 & (2 | 3) From here on...you can use the standard Infix to prefix conversion and evaluate th prefix notation.

Here is the algorithm to convert infix to prefix http://www.c4swimmers.esmartguy.com/in2pre.htm http://www.programmersheaven.com/2/Art_Expressions_p1