Thread: Printing Syntax Tree with different indentation at different levels?

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    10

    Question Printing Syntax Tree with different indentation at different levels?

    Hey guys, I'm trying to print out my syntax tree using different amounts of indentation for each level in the tree. I'm not not quite sure how to achieve this in C. I've created a for loop and a char* that has " " assigned to it... but when I try to add the char* to itself for each increment in the level it just crashes the program. Anyways, here's what I got, let me know what you guys think I should do:

    Code:
    int synTreePreOrderWalk( TREENODE * ptree, int (*func)(), int level)
    {
        char *c = "  ";
    	int i;
    	int iRet;
    	if( ptree) {	// if current node not null
    		// perform action - quit walking if non-zero return value
    		for(i = 0; i < level; i++)
    		// *c += *c;
    		if( iRet = (*func)(ptree, level)) printf("%s" "%s\n", c, ptree->label);
    		// visit children
    		level++;  // going to a new indentation level
    		
    		if( iRet = synTreePreOrderWalk( ptree->left, func, level))  printf("%s" "%s\n", c, ptree->label);
    		if( iRet = synTreePreOrderWalk( ptree->right, func, level)) printf("%s" "%s\n", c, ptree->label);
    		// set level back to my level
    		level--;  // visit siblings
    		
    		//if( iRet = synTreePreOrderWalk( ptree->sibling, func, level)) return iRet;
    	}
    	return 0;
    }

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Oh dear.

    *c is pointer with no memory assigned to it...

    [edit] quzah correctly corrects me on this, but as s/he says you still cannot add to *c as is
    Last edited by MK27; 05-23-2009 at 06:53 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Not exactly:
    Code:
    char *c = "  ";
    It's actually pointing at a string literal. And you're not allowed to modify literals.


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is a rough program that shows one way to do it. The indentation level from left to right, depends on the depth that the solution was found at.

    If you use some of the other rem'd out blocks of code, you can see it quite clearly.

    Code:
    /* Solves using brute force, the 8 tile 2D "rubik's cube" puzzle.
    Adak, Nov. 2008 
    
    Status: Rough, but works. Has a good, clear,  iterative depth first 
    search (DFS)!
    
    To Improve: Fix showB, when starting depth is 4 or less.
    */
    
    #include <stdio.h>
    
    #define MaxDepth 30
    
    //function prototypes
    void copyB(int);
    int isSolved(int);
    int move1(int);
    int move2(int);
    int move3(int);
    void showB(int);
    
    int b[2][4][MaxDepth + 1];    //b is shorthand for the board
    int t[1][4];                  //t is a temporary holding row
    int line[MaxDepth + 1];       //the line of moves that are played
    
    int main(void)  {
       int i, move, deep, depth, done, solved, reset, gar;
    // test right shift    
    /*   b[0][0][0] = 2; b[0][1][0] = 3; b[0][2][0] = 4; b[0][3][0] = 1;
       b[1][0][0] = 7; b[1][1][0] = 6; b[1][2][0] = 5; b[1][3][0] = 8;
    */
    // test row swap
    /*   b[0][0][0] = 8; b[0][1][0] = 7; b[0][2][0] = 6; b[0][3][0] = 5;
       b[1][0][0] = 1; b[1][1][0] = 2; b[1][2][0] = 3; b[1][3][0] = 4;
    */
    // test Rotate 4 inner tiles
    /*   b[0][0][0] = 1; b[0][1][0] = 3; b[0][2][0] = 6; b[0][3][0] = 4;
       b[1][0][0] = 8; b[1][1][0] = 2; b[1][2][0] = 7; b[1][3][0] = 5;
    */
    // test depth of 2, solution 1 2
    /*   b[0][0][0] = 7; b[0][1][0] = 6; b[0][2][0] = 5; b[0][3][0] = 8;
       b[1][0][0] = 2; b[1][1][0] = 3; b[1][2][0] = 4; b[1][3][0] = 1;
    */
    //test depth of 2, solution 2 3  no depth=2 solution found for 1+3
    /*   b[0][0][0] = 8; b[0][1][0] = 2; b[0][2][0] = 7; b[0][3][0] = 5;
       b[1][0][0] = 1; b[1][1][0] = 3; b[1][2][0] = 6; b[1][3][0] = 4;
    */
    //test depth of 3, solution 2 3 3
    /*   b[0][0][0] = 8; b[0][1][0] = 3; b[0][2][0] = 2; b[0][3][0] = 5;
       b[1][0][0] = 1; b[1][1][0] = 6; b[1][2][0] = 7; b[1][3][0] = 4;
    */
    //test depth of 7, (2684/1375) solution is 3 3 1 3 1 1 1
       b[0][0][0] = 2; b[0][1][0] = 6; b[0][2][0] = 8; b[0][3][0] = 4;
       b[1][0][0] = 1; b[1][1][0] = 3; b[1][2][0] = 7; b[1][3][0] = 5;
    
    //test? depth of 18 (2134/8765) solution is 231231313131231312
    /*   b[0][0][0] = 2; b[0][1][0] = 1; b[0][2][0] = 3; b[0][3][0] = 4;
       b[1][0][0] = 8; b[1][1][0] = 7; b[1][2][0] = 6; b[1][3][0] = 5;
    */
    //test 19 ply deep: 2834/1765 
    /*   b[0][0][0] = 2; b[0][1][0] = 8; b[0][2][0] = 3; b[0][3][0] = 4;
       b[1][0][0] = 1; b[1][1][0] = 7; b[1][2][0] = 6; b[1][3][0] = 5;
    */
       printf("\n\tThe puzzle is solved when it has 1234 in the first row,");
       printf("\n\tand 8765 in the second row.");
    
       printf("\n\n\tMoves are noted in this program, by number:\n\n");
    
       printf("\t1 = A right shift of both rows: 1234 becomes 4123\n");
       printf("\t                                8765         5876\n\n");
    
       printf("\t2 = A swap of the two rows: 1234  becomes  8765\n");
       printf("\t                            8765           1234\n\n");
    
       printf("\t3 = A clockwise rotation of the four central numbers:\n\n");
       printf("\t    1234 becomes 1724\n");
       printf("\t    8765         8635\n\n");
       
       printf("\tThese are the only three moves allowed in this puzzle.\n\n");
       printf("\tThe boards are displayed according to their depth in the\n");
       printf("\tsearch tree. The starting position (depth 0), is at the far\n");
       printf("\tleft. Every eight characters to the right, shows another\n");
       printf("\tdepth in the search tree, up to 10 ply deep.\n\n");
    
       printf("\n Our Starting position is:\n\n");
       showB(0);
    
       printf("\t\t\t    Press Enter to Continue\n\n ");
       gar = getchar();
    
       deep = solved = reset = 0;
       move = 1; depth = 4;
    
       while(1)  {  //main DFS loop
          ++deep;
          if(move == 1)
             solved = move1(deep);
          else if(move == 2)
             solved = move2(deep);
          else
             solved = move3(deep);
    /*
          if(move == 1)
             printf("\n Right shift:");
          else if(move == 2)
             printf("\n Row swap:");
          else
             printf("\n Rotate 4 #'s:");
    
          printf("\t Line: ");        //shows the line of moves being searched
          for(i = 0; i < deep; i++)   
             printf(" %d", line[i]);
    */
          if(solved || depth >= MaxDepth) 
             break;
    
    
          for(i = 0, done = 0; i < depth; i++)  { //are we done?  
             if(line[i] == 3)
                done = 1;
             else  {
                done = 0;
                break;
             }
          }
          if(done && depth <= MaxDepth)  {
             deep = 0;
             depth += 1;
             printf("\n Depth: %d", depth);
             done = 0;
             reset = 1;
          }
          if(reset)  {    //depth was reset, move needs to reset to 1 again
             move = 1;
             reset = 0;
             continue;
          }
          if(deep >= depth)  {
             if(move < 3)
                line[--deep] = 0;
             else
                while(line[deep-1] == 3) {
                   line[--deep] = 0;
                }
             if(++move > 3) { 
                deep -= 1;
                move = line[deep] + 1;
                if(move > 1)
                   reset = 1;
             }
          }
       }
    
       if(!solved)
          printf("\n\n\t\t\t  No Solution was Found %d", done);
    
       printf("\n\n\t\t\t       Press Enter to Quit\n");
       gar = getchar(); gar++;
       return 0;
    }
    void copyB(int d)  {  //copy the old board position, into the new depth
       int r, c;    
       
       for(r = 0; r < 2; r++) 
          for(c = 0; c < 4; c++)
             b[r][c][d] = b[r][c][d-1];
    }
    int move1(int d)  {  //shifts all numbers one column to the right &  wraps
       int r, c, solved, temp;
       solved = 0;
       copyB(d);
          
       for(r = 0; r < 2; r++)  {
          temp = b[r][3][d];
          for(c = 2; c >-1 ; c--)  
             b[r][c+1][d] = b[r][c][d];
          b[r][0][d] = temp;
       }
       
       line[d-1] = 1;
       solved = isSolved(d);
       
       return solved;
    }
    int move2(int d)  { //swaps rows
       int c, solved;
       solved = 0;
       copyB(d);
       
       for(c = 0; c < 4; c++)  {
          t[0][c] = b[0][c][d];
          b[0][c][d] = b[1][c][d];
          b[1][c][d] = t[0][c];
       }
    
       line[d-1] = 2;
       solved = isSolved(d);
       
       return solved;
    }
    int move3(int d) { //Rotates the 4 inner numbers, clockwise
       int solved, temp;
       solved = 0;
       copyB(d);
    
       temp = b[0][1][d];
       b[0][1][d] = b[1][1][d];
       b[1][1][d] = b[1][2][d];
       b[1][2][d] = b[0][2][d];
       b[0][2][d] = temp;
    
       line[d-1] = 3;
       solved = isSolved(d);
       
       return solved;
    }         
    void showB(int d)   {   //shows the board array, if needed
       int r, c, tab;
       printf("\n\n");
       if(d < 11)  {
          for(tab = 0; tab < d; tab++)
             putchar('\t');
          for(r = 0; r < 2; r++) {
             for(c = 0; c < 4; c++)  
                printf("%d ", b[r][c][d]);
             putchar('\n');
             if(d < 11)  {
                for(tab = 0; tab < d; tab++)   
                   putchar('\t');
             }
          }
       }
    }
    int isSolved(int d)  {
       int i;
       int done = 0;
       if(b[0][0][d]==1 && b[0][1][d]==2 && b[0][2][d]==3 && b[0][3][d]==4)
          if(b[1][0][d]==8 && b[1][1][d]==7 && b[1][2][d]==6 && b[1][3][d]==5)  {
             done = 1;
             printf("\n\n\t The Solution is:");
             for(i = 0; i < d; i++)
                printf(" %d", line[i]);
             showB(d);
          }
          
       return done;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. more then 100errors in header
    By hallo007 in forum Windows Programming
    Replies: 20
    Last Post: 05-13-2007, 08:26 AM
  2. Using VC Toolkit 2003
    By Noobwaker in forum Windows Programming
    Replies: 8
    Last Post: 03-13-2006, 07:33 AM
  3. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 06:39 AM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

Tags for this Thread