Algorithm to evaluate value of Boolean expression

Question

I had programming interview which consisted of 3 interviewers, 45 min each. While first two interviewers gave me 2-3 short coding questions (i.e reverse linked list, implement rand(7) using rand(5) etc ) third interviewer used whole timeslot for single question:

You are given string representing correctly formed and parenthesized boolean expression consisting of characters T, F, &, |, !, (, ) an spaces. T stands for True, F for False, & for logical AND, | for logical OR, ! for negate. & has greater priority than |. Any of these chars is followed by a space in input string. I was to evaluate value of expression and print it (output should be T or F). Example: Input: ! ( T | F & F ) Output: F

I tried to implement variation of Shunting Yard algorithm to solve the problem (to turn input in postfix form, and then to evaluate postfix expression), but failed to code it properly in given timeframe, so I ended up explaining in pseudocode and words what I wanted.

My recruiter said that first two interviewers gave me "HIRE", while third interviewer gave me "NO HIRE", and since the final decision is "logical AND", he thanked me for my time.

My questions: Do you think that this question is appropriate to code on whiteboard in approx. 40 mins? To me it seems to much code for such a short timeslot and dimensions of whiteboard. Is there shorter approach than to use Shunting yard algorithm for this problem?

Disrupt

Not a good interview question, if you are unfamiliar with the algorithm. – Orian

Answer 1

Well, once you have some experience with parsers postfix algorithm is quite simple. 1. From left to right evaluate for each char: if its operand, push on the stack. if its operator, pop A, then pop B then push B operand A onto the stack. Last item on the stack will be the result. If there's none or more than one means you're doing it wrong (assuming the postfix notation is valid).

Infix to postfix is quite simple as well. That being said I don't think it's an appropriate task for 40 minutes if You don't know the algorithms. Here is a boolean postfix evaluation method I wrote at some stage (uses Lambda as well):

public static boolean evaluateBool(String s)
{
    Stack<Object> stack = new Stack<>();
    StringBuilder expression =new StringBuilder(s);
    expression.chars().forEach(ch->
    {
        if(ch=='0') stack.push(false);  
         else if(ch=='1') stack.push(true); 
          else if(ch=='A'||ch=='R'||ch=='X')
          {
              boolean op1 = (boolean) stack.pop();
              boolean op2 = (boolean) stack.pop();
              switch(ch)
              {
                case 'A' : stack.push(op2&&op1); break;
                case 'R' : stack.push(op2||op1); break;
                case 'X' : stack.push(op2^op1); break;
              }//endSwitch  
          }else 
              if(ch=='N')
                {
                  boolean op1 = (boolean) stack.pop();
                  stack.push(!op1);
                }//endIF
    });
    return (boolean) stack.pop();
}

In your case to make it working (with that snippet) you would first have to parse the expression and replace special characters like "!","|","^" etc with something plain like letters or just use integer char value in your if cases.

Junction