Parsing/evaluating conditional statements
I need some help developing an algorithm for parsing and evaluating conditional statements. I need to be able to handle variables, logical operators, relational operators, mathematical operators, and parentheses.
For example:
if ( (a+1 > b*5) and ((c +2) * 6 <= 5) )
All the variables correspond to a number so the expression could be trivially converted to something like this:
if ( (8+1 > 4*5) and ((6 +2) * 6 <= 5) )
I am aware that infix expression can be converted to postfix expressions for easier evaluation, but I don't know exactly how this is done, nor do I know if this would be the best way to do it.
If more information is needed let me know.
Thanks in advance,
Paul
> I am aware that infix expression can be converted to
> postfix expressions for easier evaluation, but I
> don't know exactly how this is done, nor do I know if
> this would be the best way to do it.
Did you try Google?
http://www.google.com/search?hl=en&lr=&q=infix+to+postfix&btnG=Search
Yes I have searched google quite a bit, but I am having trouble finding information that is specific to my problem. If I knew that converting to postfix is actually what I should be doing that would help allot. Converting to postfix seems to be common for writing compilers which is pretty similar to what I am doing, but there is one big difference. As far as I understand, it makes sense to convert to postfix for a compiler since assembly operates in postfix, but my expressions will be evaluated in java not machine code and java uses infix notation.
I have actually experimented with writing a recursive algorithm to process the expressions by order of precedence but I ran into some problems. Some operators return a numerical result, while others need to return a boolean result, and parrens can actually return either depending on what they are surrounding. Java methods seem inadequate for this since they can only return one type, so I used objects. Using objects however seems pretty cumbersome for this and I am still having trouble getting parrens to work correctly.
Thanks,
Paul
You don't need to use postfix unless you're simulating a stack machine (eg the JVM). A native compiler would target registers. For simple expressions, you can build a tree which represents the structure of the expression, and then evaluate it by direct recursion. Use operator precidence to either recurse left or right on the sub-tree. I hacked an example at http://www.tincancamera.com/examples/java/expressions/ExpressionParser.java.txt , at 500 lines it's rather too long to post here.
Pete
<url space punctuation>
Thanks, this is very helpful information. I ended up coding it by converting to postfix already and have had good results, but I will look into the tree method when I get some time and see if it works better for me. Also if you know what method would typically yeild the best performace for evaluation of the expressions, let me know.
Also, for anyone else that might want to do this I coded a simple stack class to get around creating objects for evaluating integer/boolean expressions, as long as its not a problem if exceptions are not thrown if the expression's logic is messed up.
Thanks again,
Paul
public class IntStack
{
private int[] stack;
private int top;
public IntStack(int maxSize)
{
stack = new int[maxSize];
top = 0;
}
public void push(int value)
{
top++;
stack[top] = value;
}
public int popInt()
{
top--;
return stack[top+1];
}
public void push(boolean value)
{
top++;
if (value)
stack[top] = 1;
else
stack[top] = 0;
}
public boolean popBool()
{
top--;
return stack[top+1] == 1;
}
public boolean isEmpty()
{
return top == 0;
}
}
