Thread: Stacks

  1. #1
    Registered User
    Join Date
    Feb 2005
    Posts
    26

    Stacks

    I'm just learning the concept of stacks and I'm having a bit of trouble trying to figure out how to use them. I understand that you push values into the stack and you pop the upper most one. It's implementing them that I'm having some issues with.

    I have an assignment to do and I need to find my way through a maze using stacks. There are five different symbols I'm using, S is for the start point, G is for the goal, 0 is for the paths, 1 is for the walls and V is for the visited paths.

    I already have to code for the stack written but I can't figure out what order to check the paths for the maze in. Here I'll show you what I mean, here's a sample maze:

    Code:
    1 1 1 1 1 1 1 1 1 1
    1 S 0 1 1 1 1 1 1 1
    1 1 0 0 1 1 1 1 1 1
    1 1 1 0 0 0 0 1 1 1
    1 1 1 0 1 1 1 1 1 1
    1 1 1 0 1 1 1 1 1 1
    1 1 1 0 0 0 G 1 1 1
    1 1 1 0 1 1 1 1 1 1
    1 1 1 0 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1
    Now I want to get from S to G by using the stack. In the stack I want to push the x and y coordinates. That's the easy part though, I can already do that. The problem is trying to find the path. When pushing the coordinates into the stack would I want to start with S or G or some 0? Now after pushing in the initial value would I want to check all 4 values around it to see if they're 0's and push them or just push a certain 0? I've been trying to figure out a method to get it to go to G but it's hard to understand using the stack. At the end this is what I'm supose to get:

    Code:
    1 1 1 1 1 1 1 1 1 1
    1 S v 1 1 1 1 1 1 1
    1 1 v v 1 1 1 1 1 1
    1 1 1 v v v v 1 1 1
    1 1 1 v 1 1 1 1 1 1
    1 1 1 v 1 1 1 1 1 1
    1 1 1 v v v G 1 1 1
    1 1 1 0 1 1 1 1 1 1
    1 1 1 0 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1
    The V means that that 0 has been visited already. I'm supose to use back tracking so if I hit a dead end I go back to the last known area where I can travel down a new path.

    What I'm thinking is that I should start with the G and push the coordinates of that into the stack first. Then I should check the symbols in this order: up , down, left, right. If there is a 0 it should push that symbol's coordinates into the stack then check around that symbol. If I hit a dead end I should pop the coordinates until I reach a V with a 0 next to it. I should continue doing that until I reach the S. Do you think that would work?

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Just push a direction of movement on the stack. Push always in the same order of direction: N, E, S, W. That is to say, if you've moved to a new cell, look north first. If there is a way to go, go that way. If not, check east. If not, check south, if not, check west, if not, you have to backtrack (pop).

    It doesn't really matter at all what order you go in, as long as it's a fixed direction. You may want to run through your stack though, to make sure you're not pushing a location you already have.

    So, perhaps pushing a pair of coordinates would be better. Consider the following:
    Code:
    11111
    10001
    10101
    G0001
    1S111
    Now then, there is potential here for you to simply go from start:
    3 N, 2 E, 2 S, 2 W, 2 N, ... repeat indefinately.

    So here, what you may want to do, is add a check to see if any of the neighboring squares are the goal. If so, immediately go that direction. Combine this with checking to see if you have in fact been here already, will prevent you from running in circles forever.

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

  3. #3
    Registered User
    Join Date
    Feb 2005
    Posts
    26
    Alright thanks, I'll write the code to see if I run into any problems.

  4. #4
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    code will look something like this

    Code:
    initial call: find_path(start, finish, maze)
    
    bool find_path(Stack &path, 2DVector finish, Matrix maze) {
      
      // check if goal was reached
      2DVector current_position = path.top();
      2DVector next_position;
    
      if(path.top() == finish) 
        return SUCCESS;
    
      2DVector direction[4] = {(-1, 0), (1, 0), (0,1), (0, -1) }
    
      for(int x = 0; x < 4; ++x) {
          next_position = current_position + direction[x];
    
    
          if(maze(next_position) != 1) {
            path.push(next_position);
            // the next_position lead to success!!!
            if(SUCCESS == find_path(path, finish, maze))
              return SUCCESS;
           }
    
           // the next_position didnt lead to success - remove it again
           path.pop();
    
        }
    
      return FAILED;
    }
    [edit]
    sry for those who read the previous code - that one was messed up
    [/edit]
    Last edited by Raven Arkadon; 02-26-2005 at 01:55 PM.
    signature under construction

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Stop posting C++ code on the C board.

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

  6. #6
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    sheesh.. its PSEUDO CODE
    well it was intended to be it
    Last edited by Raven Arkadon; 02-26-2005 at 01:56 PM.
    signature under construction

  7. #7
    Registered User
    Join Date
    Feb 2005
    Posts
    26
    It wasn't the code I was having problems with just the concept but I understand it now.

  8. #8
    Registered User
    Join Date
    Feb 2005
    Posts
    26
    I've run into a bit of a problem. It's either something wrong with how I'm reading in the characters or how I'm printing them. Here's the code:

    Code:
    void findmaze(char symbol[LENGTH][LENGTH])
    {
    	int row, col;
    
    	for(row = 0; row < LENGTH; row++)
    		for(col = 0; col < LENGTH; col++)
    			symbol[row][col] = getc(infile);
    			
    	for(row = 0; row < LENGTH; row++)
    		for(col = 0; col < LENGTH; col++)
    			putchar(symbol[row][col]);
    
    }
    When I run the function here's the output I get:

    Code:
    11111111111111111111
    11111S01111111101111
    11111101111111101111
    11111100000000001111
    11111110111111101111
    11111110111111101111
    11111110111111101111
    11111111111111101111
    11111111110000001111
    11111111110111101111
    11111111110111101111
    11111111110111101111
    11111111111111101111
    11111111111111101111
    11111G11111111101111
    11111011111111101111
    11111000000000001111
    11111111111111111111
    1111
    Here's the output I want:

    Code:
    11111111111111111111
    11111S01111111101111
    11111101111111101111
    11111100000000001111
    11111110111111101111
    11111110111111101111
    11111110111111101111
    11111111111111101111
    11111111110000001111
    11111111110111101111
    11111111110111101111
    11111111110111101111
    11111111111111101111
    11111111111111101111
    11111G11111111101111
    11111011111111101111
    11111000000000001111
    11111111111111111111
    11111111111111111111
    11111111111111111111
    You can see how it cuts off the last row and part of the one above it. Why is it doing that? I've tried changing the code around but everything else seems to make it worse.

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Is this a text file, where each "ROW" of your maze is on a seperate line? If so, you're forgetting about the newline that's in the file. You should read that and display it. See, you don't have anything in your code to pay attention to the newline, or to actually display a newline when you are trying to output it.

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

  10. #10
    Registered User
    Join Date
    Feb 2005
    Posts
    26
    That doesn't seem to be working either or I'm doing it terribly wrong lol. Here's the new updated code:

    Code:
    void findmaze(char symbol[LENGTH][LENGTH])
    {
    	int row, col;
    
    	for(row = 0; row < LENGTH; row++){
    		for(col = 0; col < LENGTH; col++)
    			symbol[row][col] = getc(infile);
    			
    		getc(infile);
    	}
    			
    	for(row = 0; row < LENGTH; row++){
    		for(col = 0; col < LENGTH; col++)
    			putchar(symbol[row][col]);
    			
    		putchar('\n');
    	}
    
    }
    That should take the end line off after it gets the 20 characters from each line but it doesn't. Here's the output I get:

    Code:
    11111111111111111111
    
    11111S0111111110111
    
    111111011111111011
    1
    11111100000000001
    11
    1111111011111110
    111
    111111101111111
    1111
    11111110111111
    01111
    1111111111111
    101111
    111111111100
    0001111
    11111111110
    11101111
    1111111111
    111101111
    111111111
    0111101111
    11111111
    11111101111
    1111111
    111111101111
    11111G
    1111111101111
    11111
    11111111101111
    1111
    000000000001111
    111
    1111111111111111
    11
    11111111111111111
    1
    I don't see why it shouldn't work.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Please Help Me With This Code Of Implementing Stacks
    By raghu_equinox in forum C Programming
    Replies: 3
    Last Post: 10-19-2006, 07:22 AM
  2. ...multiplication using stacks
    By iiwhitexb0iii in forum C Programming
    Replies: 1
    Last Post: 10-09-2006, 01:28 AM
  3. Avioding Stacks
    By LoafOfBread34 in forum C++ Programming
    Replies: 8
    Last Post: 12-08-2004, 06:20 AM
  4. Dumping singly linked list into 2 stacks.
    By strotee76 in forum C++ Programming
    Replies: 5
    Last Post: 05-16-2004, 05:48 PM
  5. Stacks stacks stacks
    By Unregistered in forum C Programming
    Replies: 4
    Last Post: 06-06-2002, 02:01 AM