boolean postfix notation

Question

I have to write an ADT character stack to handle postfix notation for boolean values.

This is an example of one of the postfix notations.

T T && F || ! ( this will be the input text)

I know that this evaluates to false.

My question is.

What does this notation end up looking like in code. (once the input string has been parsed)

My guess is:

if ( !( true && true || false) )
    //do something;
else
    //do something else

I'm fairly sure this is wrong and I am way off the mark, I have tried all sorts of combinations. I can't get it to return false.

Answer 1

You usually interpret RPN stack-wise, with binary operators popping two arguments off the stack, and unary one.

1. T T — pushes two true values onto the stack, stack is: T T,
2. && — pops two values, pushes and: T && T, stack is: T,
3. F — pushes false onto the stack, stack is: T F,
4. || — pops two values, pushes or: T || F, stack is: T,
5. ! — pops one value, pushes negated version: !T, stack is: F.

So your final result is the result of these operations (written from bottom to top):

bool result = !(false || (true && true));

---

You just need to read it from the end; it might be a bit easier when converted to prefix notation first (from bottom to top):

! ( || ( F && ( T T ) ) )

Then you an just move the binary operators inside the parentheses:

! ( || ( F && ( T    T ) ) )
     -----> ----->
! (      F || ( T && T ) )

Answer 2

Your main problem shoud be because you're returning the opposite from what the if condition evaluates to (see ablm comment). But in general you should wrap every evaluated expression in parenthesis to ensure a correct result:

return !((true && true) || false);

This way, even if the precedence of the operators in your target language (C/C++) is different from the intended order of computation, the expression will still be evaluated how you want to.

Answer 3

if ( !( true && true || false) ) <-- this is false
    return false; <-- this evaluates if expression inside if is true, which is not
else
    return true; <--- if expression inside if is false then this(true) is returned.

So for proper return type you will need to interchange returns.

if ( !( true && true || false) )
    return true;
else
    return false;