C++ infix to prefix 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?

Polymorphous

By convention TAB and NEWLINE are types of WHITESPACE. Did you really mean the SPACE character? Please clarify your question with that information. – Frostwork

Converting infix to prefix is a neat homework assignment, but useless in the real world. Options: (A) Parse infix and go (B) Parse infix, translate to prefix, produce prefix, parse prefix, go. Even if parsing prefix is easier, the conversion process is slower. – Abrogate

Answer 1

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.

Frostwork

Answer 2

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

Dupaix

in order to evaluate a condition, you must parse the text... hence a parser of some sort is needed... Additionally conversion from infix to prefix requires parsing as one must know the associativity rules and precedence of the operators to do ti correctly... – Frostwork

I dint say we dont need parsing. I said we dont need a full fledged parser like lex/yacc. doing an infix to prefix conversion using this is a joke. i.e we dont need to construct AST in this case. – Dupaix

Answer 3

Use a parser generator like the Lex/Yacc pair.

Tokyo

I am more afraid of Lex/Yacc sort of parsers. I knew they exist but I don't know how to use them efficiently. – Polymorphous