Subscribe to The Blog without a good name        RSS Feed
-----

Applications for Stacks - Boredom Inspired ++

Icon Leave Comment
C++ Stack Cookbook
What the hell can you do with stacks?

Part 1: What this is

Okay, so I'm bored and I've got something in mind. I figure i'll fill up another blog post with applications of stacks. I'm going to cover several, which will be listed at the end of this. Anyways, this is not the end all and be all definitive guide. I'm sure if we get down to it there are an infinite number of applications for a stack object. As for me, I don't have enough time to deal with infinity, so I choose a few of my favorite.

What we'll be doing
1) Evaluating Postfix Expressions
2) Turning infix expressions into postfix expressions
3) Stacks and Recursion
4) Converting from Decimal to Binary using stacks

Also, as a quick note, I'll be using the STL stack because I don't feel the need to reinvent the wheel. This is not about how to define the ADT Stack, but instead about four applications of it.

Part 2: Evaluating Postfix Expressions

Postfix. This is probably going to need a little explaining so i'll start with an example Take the following infix equation.

1+2



We know that equals 3. So let's look at the postfix expression.

12+



As you can see, the only thing that changed was the placement of the operator. It still equals 3. Basically, to evaluate a postfix expression, you scan it, find the first operator and apply that operator to the last two numbers. Then you repeat the process over and over until you run out of operators. This is of course left-to-right still, we haven't entered the eighth dimension of math or something weird like that. So now that we know how to solve them, if you know anything about stacks, you're probably already seeing the correlation there.

So let's look at an alogrithim for this.

Read in expression
for i = 0 to size of expression - 1
   if char at position i is a number
	  push it onto the stack
   else
	  evaluate operator and apply to last two numbers in stack
   end if
end for



The only time consuming coding task here is that since the operator will be a char constant, we'll have to either use a switch or an if block to determine which one it is. So let's implement some code.

#include <stack>
#include <string>
#include <iostream>
#include <sstream>

using namespace std;

int main()
{

   string expression;
   stack<int> ours;
   cout << "Enter a postfix expression: ";
   getline(cin,expression);
   cout << endl << endl;
   
   stringstream ss(line,stringstream::in);
   while(!ss.eof)
   {
   
	  string token;
	  ss >> token;
	  
	  if( atoi(token.c_str()) != 0 ) ours.push(atoi(token.c_str()));
	  else //must be an operator
	  {
	  
		 //pick which operator it is, then do the following. i'll just do +
		 
		 if( token == "+" )
		 {
		 
			int x = ours.pop();
			
			ours.push(x+ours.pop());
			
		 }
		
	  }
	  
	}
	
	cout << "The expression " << expression << " evaluates as " << ours.pop() << endl;
	
}



So that's our postfix expression evaluator. You may be wondering why I use stringstream. The answer is so that I can use c_str to use atoi. If I were to have used the indexed version of a char in expression, such as expression[i], atoi would not work. Now, let's talk about converting infix to postfix.

Part 3: Converting InFix to Postfix

So let's take a look at using stacks to convert InFix to Postfix. To begin with, let's look at the expression 4+5+(3+4). Hmm, looks complicated. It's not really, I promise. So how do we go about converting this? Well let's run through a stack real quick and see what happens.

Stack: empty
Expression: 4+5+(3+4)
At Token: 4
cout:

Pass 1: Display 4

Stack: empty
At Token: +
cout: 4

Pass 2: Push + onto stack

Stack: +
At Token: 5
cout: 4

Pass 3: Display 5

Stack: +
At Token: +
cout: 45

Pass 4: Display + and Push + onto the stack

Stack: +
At Token: (
cout: 45+

Pass 5: push ( onto stack

Stack: +(
At Token: 3
cout: 45+

Pass 6: Display 3

Stack: +(
At Token: +
cout: 45+3

Pass 7: Push + onto the stack

Stack: +(+
At Token: 4
cout: 45+3

Pass 8: Display 4

Stack: +(+
At Token: )
cout: 45+34

Pass 9: Pop and display stack until a (

Stack: +
At Token: N/A
cout: 45+34+

Pass 10: Pop and display items in stack until empty

Stack: empty
At Token: N/A
cout: 45+34++

So we're done. Whew, that's some work. Glad the computer does it for us once it's code. So let's talk about the algorthim i'm using. It should be pretty apparaent as to the basic idea, but let me actually spell it out.

1. Make an empty stack
2. For the entire string, go through each token
   a. Get token
   b. If token is
      i. a (: Push onto stack
	  ii. a ): pop and display until ( is reached in stack
	  iii. An operator:
	     ichi: stack empty? Push it onto stack
		 ni: operator on top of stack has higher priority than the token? Pop the operator in the stack and display it
		 San: Keep repeating for all operands in stack until it is either empty or the operand has a lower priority than token, in which case you push token.
	  iv: An operand (number): display it
3. Pop and display stack until empty



Yeah, so we've done it. Let's do a little coding.

//includes

//using std

int main()
{

stack<int> empty;
string expression;
getline(cin,expression);

for( int i(0); i < expression.length(); i++ )
{

//use algorithim

}

while( !ours.empty ) cout << ours.pop();

}



A little less on the code side, but the algorithim is pretty self explanatory. Note that you use the same code as in 1, just that you change your algorithim around.

Part 4: Stacks and Recursion

This is a purely educational section. I'm sure that if you're reading this, you already know what recursion is. So i'm going to skip past explaining it and tell you how it's dealt with. As you probably guessed, it has something to do with a stack. So let's say we have function F here.

int f(int x)
{
   
   if( x > 1 || x == 0) return f((x/2)-1);
   else return 15;
   
}



So a nice little recursive function. if you'll notice, basically this works by making even numbers wind down to 0 and odd numbers wind down to 1. Why? Well, that's because odd is defined as:

Any integer K such that k = 2a+1.

And even is defined as:

Any integer K such that k = 2a.

So what am I doing? Basically reversing the process on some level. Anyways, that's uninimportant, just know that given an integer, it will eventually reach 0 or 1. DO NOT PUT IN A NEGATIVE INTEGER! - FRIENDLY WARNING :)

Anyways, what eventually happens is that it reaches your function and evaluates it. Then it decides to return the recursive function. What happens at this point? Well, the state of the function call that it's currently in is pushed onto the stack, then the next function call is determined. This continues ad infinitum until it reaches the base case, that is x <= 1 or x == 0. At that point, it returns 15 to each function currently in the stack. So basically, this function returns 15. It's just got to go through hoops to do it. That's all for this section. No really, I just wanted to tell you how they were handled. :)

Part 5: Converting Decimal to Binary

Yeah, something fun! At least for me. So, there's a method to convert decimal to binary that involves dividing the binary by 2 and pushing the remainded onto a stack. Let's look at a quick example of this.

Take x = 26. This is what will happen.

push 26%2 onto stack. (0)

x = x/2

push x%2 onto stack. (13%2 = 1)

x=x/2

...etc...until x = 0

Then go through the entire stack and output everything in it. In the end, 26 ends up being 11010 in binary.

So that's pretty simple as an alorithim. Let's take it for a spin.

//same includes

//using std

int main()
{

   stack<int> ours;
   int x;
   cin >> x;
   
   while( x != 0 )
   {
   
	  ours.push(x%2);
	  x=x/2;
	  
   }
   
   while( !ours.empty() ) cout << ours.pop() << endl;
   
 }



Nice and quick. Well that's all for me for now. Maybe next time I get bored i'll do something like SDL, MCI or Editing Memory Addresses in C++ using Win API. Anyways, toodles.

0 Comments On This Entry

 

August 2014

S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930
31       

Tags

Recent Entries

Search My Blog

0 user(s) viewing

0 Guests
0 member(s)
0 anonymous member(s)