Solve with Python and use eval() to calculate boolean expression

Please, could you send your problem(AC code)

Here is the right description:

1) A, ..., Z, TRUE, FALSE - are correct boolean expressions;

2) if x and y are correct boolean expressions, then the correct boolean expressions are also:
  (x);  NOT x;  x AND y;  x OR y  (maybe, with some extra spaces).

Edited by author 19.09.2007 23:19

WHO CAN GIVE ME A TEST....
THANK YOU VERY MUCH

Hello all :) I'm new to timus online judge.. My program work well in my system but when I submit it displays a RUN TIME ERROR i'm totally confused please help me :( :(
here is my program

import java.util.*;
import java.io.*;
import java.util.regex.*;

public class RobotInTheField {
  public static void main(String args[])
   throws IOException {
     String data = "";
     Field field;
     int N,M,K;
     Scanner sc = new Scanner(System.in);
     boolean registers[] = new boolean[26];
     Robot robot;
     Pattern p;
     Matcher m;
     BufferedReader br;
     ExpressionEvaluation expressionevaluation=new ExpressionEvaluation();
     br=new BufferedReader(new InputStreamReader(System.in));

     data = br.readLine(); // reading problem inputs

     N = sc.nextInt();
     M = sc.nextInt();
     K = sc.nextInt();

     field = new Field(N);

     for(int i=0;i<M;i++) { // setting forks at the specified x and y location
       int x = sc.nextInt();
       int y = sc.nextInt();
       field.set(x,y,'f');
     } //for loop ends

     for(int i=0;i<K;i++) {
       String d = br.readLine();
     /* Removing white spaces */
        String split[] = d.split(" ");
        int x;
        String dummy ="";
        if(split[0].charAt(0) == '-'){

          for(int j=1;j<split[0].length();j++) {
            dummy += split[0].charAt(j);

          }
           x = Integer.parseInt(dummy);
           x = x*-1;
        }
        else {
          x = Integer.parseInt(split[0]);
        }
        dummy = "";
        int y;
        if(split[1].charAt(0) == '-'){

          for(int j=1;i<split[1].length();j++) {
            dummy += split[1].charAt(j);

          }
           y = Integer.parseInt(dummy);
           y = x*-1;
        }
        else {
          y = Integer.parseInt(split[1]);
        }

       char register = split[2].charAt(0);
       //System.out.println("x:"+x+",y:"+y+",ch:"+register);
       field.set(x,y,register);
     } //for loop ends




     p = Pattern.compile("TRUE");
     m = p.matcher(data);
     data = m.replaceAll("t");
     p = Pattern.compile("FALSE");
     m = p.matcher(data);
     data = m.replaceAll("f");
     p = Pattern.compile("NOT");
     m = p.matcher(data);
     data = m.replaceAll("!");
     p = Pattern.compile("AND");
     m = p.matcher(data);
     data = m.replaceAll("&");
     p = Pattern.compile("OR");
     m = p.matcher(data);
     data = m.replaceAll("|");
     p = Pattern.compile(" ");
     m = p.matcher(data);
     data = m.replaceAll("");

     robot=new Robot();
     robot.direction="right";
     while(robot.xpos >= (-1*N) && robot.xpos <= N &&
           robot.ypos >= (-1*N) &&robot.ypos <= N) {
         System.out.println(robot.xpos+" "+robot.ypos);

      // If robot found the fork it needs to change its direction
         if(field.get(robot.xpos,robot.ypos)=='f'){
           //   System.out.println("WARNING:ROBOT HITS THE FORK");
           // robot first evaluate its expression
               String e = expressionevaluation.postfixConversion(data);

               if(expressionevaluation.postfixevaluation(e,registers)) {
                  if(robot.direction.equals("right"))
                     robot.direction="down";
                  else if(robot.direction.equals("left"))
                     robot.direction="up";
                  else if(robot.direction.equals("up"))
                     robot.direction="right";
                  else if(robot.direction.equals("down"))
                     robot.direction="left";
              }
              else {
                  if(robot.direction.equals("right"))
                     robot.direction="up";
                  else if(robot.direction.equals("left"))
                     robot.direction="down";
                  else if(robot.direction.equals("up"))
                     robot.direction="left";
                  else if(robot.direction.equals("down"))
                     robot.direction="right";

              }
         }

         else if(field.get(robot.xpos,robot.ypos) == '-') {
            //do nothing just move
         }
         else {
            char invertregister=field.get(robot.xpos,robot.ypos);
            if(registers[invertregister-'A'])
              registers[invertregister-'A']=false;
            else
              registers[invertregister-'A']=true;

         }

         if(robot.direction.equals("right"))
            robot.moveright();

         else if(robot.direction.equals("left"))
            robot.moveleft();
         else if(robot.direction.equals("up"))
            robot.moveup();
         else if(robot.direction.equals("down"))
         robot.movedown();

     }
 //    System.out.println("WARNING : ROBOT ESCAPES");
 //    System.out.println("ROBOT POSITION "+robot.xpos+","+robot.ypos);
  }//main method ends here

} //testexpr class ends here
class ExpressionEvaluation { // Expression evaluation methods

  String postfixConversion(String expr) { // converting infix expression to postfix expression
      String postfixstring = "";
      StackDataStructure stackobj=new StackDataStructure(expr.length());
      boolean infinite = true;

        for(int i=0;i<expr.length();i++) {  // visiting each character in the string
            infinite = true;

            switch(expr.charAt(i)) {

                case '!' : stackobj.push('!');  // '!' is encountered just push them into the stack
                           break;

            case '&' : while(infinite) { // '&' is encountered just push them into the stack
                            if(stackobj.top == 0 || stackobj.stack[stackobj.top-1] != '!') {
                              stackobj.push('&');
                              infinite = false;
                            }
                            else
                              postfixstring += stackobj.pop() + "";
                           }
                           break;

                case '(' : stackobj.push('('); // '(' is encounterd them into stack
                           break;

          case '|' : while(infinite) { // '|' is encountered
                       if(stackobj.top == 0 || ((stackobj.stack[stackobj.top-1] != '&') && stackobj.stack[stackobj.top-1] != '!')) {
                          stackobj.push('|');
                          infinite = false;
                       }
                       else
                             postfixstring += stackobj.pop() + "";
                           }
                     break;

          case ')' : while(infinite && stackobj.top != 0) { // ')' is encountered pop elements until left parenthesis is encountered
                       char ch=stackobj.pop();

                       if(ch == '(')
                          infinite = false;
                       else
                           postfixstring += ch + "";

                      }
                      break;


          default :  postfixstring += expr.charAt(i) + "";  // operands encountered
              }// switch case end
        }// for loop end

        while(stackobj.top != 0) // pop remaining all elements from the stack
             postfixstring += stackobj.pop() + "";

      return postfixstring;
  }// postfixexpression method ends

  boolean postfixevaluation(String expr,boolean reg[]) { // postfix expression evaluation
      char e[] = expr.toCharArray(); // converting string into char array it makes easy to compute

      for(int i=0;i<e.length;i++) {
          if(e[i]=='!') { // if NOT OPERATOR found
            for(int j=i-1;j>=0;j--) {
              if(e[j]=='t'||e[j]=='f') {
                if(e[j]=='t')
                  e[i]='f';
                else
                  e[i]='t';
                  e[j]='*'; //we use that operand so we put there '*' to indicate there is no operand
                break; //NOT OPERATOR found its operand and operate on it so no need to search operand just breaking out
              } //end inner if
            } // end for loop
          } //end outer if

          else if(e[i]=='&') { // if AND OPERATOR found
            int count = 0; // just counting operands
            int op[] = new int[2]; // just use to store its operands location
            for(int j=i-1;count<2&&j>=0;j--) { // searching two operands if two operands found the search stops
              if(e[j]=='t'||e[j]=='f') { //if operands are found
                  op[count++]=j;
              }
            }
            if(e[op[0]]=='t'&&e[op[1]]=='t') // AND OPERATION done here
              e[i] = 't';
            else
              e[i] = 'f';

            e[op[0]]='*';
            e[op[1]]='*';
          }

          else if(e[i] == '|') { // if OR OPERATOR found
            int count=0;
            int op[]=new int[2];

            for(int j=i-1;count<2&&j>=0;j--) { // searching for two operands
              if(e[j]=='t'||e[j]=='f') {
                  op[count++]=j;
              }
            }
            if(e[op[0]]=='t'||e[op[1]]=='t') // OR OPERATION done here
              e[i]='t';
            else
              e[i]='f';

              e[op[0]]='*';
              e[op[1]]='*';
          }

          else {
            if(Character.isUpperCase(e[i]))
             if(reg[e[i]-'A']) {
              e[i]='t';
             }
             else {
              e[i]='f';
             }
          }


      } // for loop ends here

     if(e[e.length-1] == 't') // return boolean postfix expression evaluation
      return true;
     else
      return false;
  }//postfixevaluation method ends
}//expressionevaluation class ends

/* Implementing stack data structure */
class StackDataStructure {
    char stack[]; // stack data structure representation using arrays
    int top; // represent top element of the stack

    StackDataStructure(int len) { // initializing stack array
        stack = new char[len];
    }

    void push(char data) {  // insert element into the stack
        if(top == stack.length) {
          System.out.println("Stack overflow");
          System.exit(-1);
        }
        else {
            stack[top++] = data;
        }
    }

    char pop() { // retrieving and removing stack top element from the stack
        if(top == 0) {
            System.out.println("Stack underflow");
            System.exit(-1);
        }
        return stack[--top];
    }

    void print() { // printing stack elements
      System.out.println("Stack elements :");
        for(int i = 0; i < top; i++ ) {
            System.out.println(stack[i]);
        }
    }
}

/* Field class represents the farm field where the robot works */
class Field {
  char field[][]; // representing field in two dimension
  int N;

  Field(int n) {
    N = n;
    field = new char[N*2+1][N*2+1]; //  initializing field
    for(int i=0;i<N*2+1;i++) {    // fill empty items in the field
      for(int j=0;j<n*2+1;j++) {
        field[i][j]='-';
      }
    }
  }

  void print() { // printing the entire field view
   for(int i=0;i<N*2+1;i++) {
      for(int j=0;j<N*2+1;j++) {
        System.out.print(field[i][j]);
      }
      System.out.println();
    }
  }

  void set(int x,int y,char ch) {  // set item in the field at the given x,y position
    field[x+N][y+N]=ch;
   // System.out.println("x:"+x+"y:"+y);
  }

  char get(int x,int y) { // get item from the field by specifying x,y position
    return field[x+N][y+N];
  }

  void printdebug() {
    for(int i=0;i<N*2+1;i++){
      for(int j=0;j<N*2+1;j++){
        System.out.print(get(j-N,i-N));
      }
      System.out.println();
    }
  }
}
class Robot {
  int xpos = 0;
  int ypos = 0;
  String direction = "";

  void moveright() {
    xpos++;
  }

  void moveleft() {
    xpos--;
  }

  void moveup() {
    ypos++;
  }

  void movedown() {
    ypos--;
  }
}

what means "falls out of the field".
is that means the robot need to get to the [n,n]or [-n,-n]?

I had a small bug in my code. I found it using my test sample. I would like to share it with you. I have used some extra white space in the boolean expression. I am not sure if it is necessary, you can remove them.

Input:

(NOT  ( (NOT  NOT TRUE ) AND  A) OR (B AND C AND D))    OR E
 3 10 14
 -3 -3
 -3 -1
 -3 3
 -1 1
 0 -2
 2 -1
 2 3
 3 -3
 3 0
 3 2
 -3 -2 A
 -2 -3 A
 -2 -1 A
 -1 -3 D
 -1 -1 Z
 0 -3 C
 0 -1 C
 1 -3 E
 1 0 A
 2 -3 B
 2 0 A
 2 1 E
 3 -1 E
 3 3 B
 0 0
 1 0
 2 0
 3 0
 3 1
 3 2
 2 2
 1 2
 0 2
 -1 2
 -2 2
 -3 2


Output:
0 0
1 0
2 0
3 0
3 -1
3 -2
3 -3
2 -3
1 -3
0 -3
-1 -3
-2 -3
-3 -3
-3 -2
-3 -1
-2 -1
-1 -1
0 -1
1 -1
2 -1
2 0
2 1
2 2
2 3
3 3

This is how the table looks like: (1 means there is a Fork and * means empty cell)
1 A 1 * * * 1
A * A * * * *
D * Z * 1 * *
C 1 C * * * *
E * * A * * *
B * 1 A E * 1
1 * E 1 * 1 B

Last symbol of first string is space.

For example, the first and the third tests have some trash after them.
So, my multitest falls.

If you have WA after rejudge (or if you simply have WA and don't know why) try to test your solution with this expression:

NOT NOT A

GL ;-)

My algo uses stack to calculate the expression. I'm sure that it is right, but is has WA14.
What is a trick of this test? Please, help me!

Evaluation of this expression isn't a problem :

1) Replace all of operators into one-char operators. For example, NOT into '-', TRUE into '1', etc.
It will greatly simplify coding, because of operators don't begin on char, that can be a register.

2) Recursive descent :
In function we've got bounds of the expression and we'll find result of it in this bounds.
Find the least priority operator first. This is an operator, that has least number of not closed brackets, and if we find operator with equal number of such brackets the least in priority of operators.
Then : if not found any operator, then expression has only register or constant. Calculate it.
if NOT - Result = not Evaluate(pos_of_operator, right bound),
if OR or AND - Result = Evaluate(left_bound, pos_of_operator - 1) OPERATOR Evaluate(pos_of_operator + 1, right_bound) (crazy pseudocode =) )

That's all. Of course, it's a slow method, but it's very easy - without any problems, debugging or testing i've got fast AC 0.015 sec, 300kb

I failed many times on #14..
Can anyone help me...?

Thank you..

I've got AC using PASCAL, but got WA using C++. I used different ways to solve this problem. It seems that the answer is always same, but I don't know why my C++ program got WA on Test #14. So, can you send me the test cases?

Tests with some new types of boolean expression were added.
More than 200 authors lost AC after rejudge. Check your
expression-calculation algorithms once again.

Admins, why does my program that was AC earlier gets WA 10 now? This problem was not rejudged... Please answer my question.