ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1101. Robot in the Field

RUN TIME ERROR
Posted by hariharasathyanarayanan 21 Dec 2015 18:52
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--;
  }
}
Re: RUN TIME ERROR
Posted by Jane Soboleva (SumNU) 21 Dec 2015 22:09
That's, uh, quite a lot of code. Almost 4x times bigger than my solution.
Well, it seems to be working alright, but it's kinda hard to track down the problem.. I suggest you to comment most of the parts, then uncomment them little by little, to notice the moment when it changes from WA #1 to runtime #1, and after detecting the block which turns it into runtime, it might be easier to say what's the matter.