From what I read in a few books, a static variable retains its value(s) throughout the lifetime of a program.

In this stack program I've been trying to fix up, the static var doesn't seem to change or hold its contents after different function calls. I can't figure out what's wrong :cry:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LEN 100

void push(int);
int pop();

static int s[LEN];
static int N;

int main(void)
{
	char input[LEN];
	int i = 0, size;

	puts("Enter a postfix expression");
	scanf("%s", input);
	size = strlen(input);

	while (i < size)
	{
		if (input[i] == '+')
			push(pop() + pop());
		if (input[i] == '*')
			push(pop() * pop());
		if ((input[i] >= '0') && (input[i] <= '9'))
			push(0);
		while ((input[i] >= '0') && (input[i] <= '9'))
			push(10*pop() + (input[i++]-'0'));
		i++;
	}

	printf("Final value is %d\n", pop());
	return 0;
}

void push(int item)
{ s[N++] = item; }

int pop()
{ return s[--N]; }

From what I read in a few books, a static variable retains its value(s) throughout the lifetime of a program.

There are several different uses for the static keyword. When applied to a global variable, static means that the variable has internal linkage. In other words, the variable is only visible to the code in that file. In C, global names are always given external linkage by default, so it's good practice to make every global name static if it isn't used by other files in the program. This is the form of static that you're actually using.

The static that you're talking about is applied to a local variable in a function. The lifetime of the variable becomes static, that is, the variable lives as long as the program, and it retains its value between calls of the function even though its visibility is still restricted to the function that it's declared in. For example:

#include <stdio.h>

void foo(void)
    {
    static int y = 5;
    int z = 5;
    printf("y:%d -- z:%d\n", y++, z++);
    }

int main(void)
    {
    foo();
    foo();
    foo();
    foo();
    return 0;
    }

But that doesn't have anything to do with the problem you have, which is localized here:

scanf("%s", input);

scanf is a tricky function to work with because it doesn't follow the rules of the rest of the I/O library. In this case, you expect %s to give you a line when it actually gives you a word. Input with %s is delimited by whitespace, so if you type "10 2 *", the contents of input after scanf returns will be "10". To read an entire line, you would best use fgets:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LEN 100

void push(int);
int pop();

static int s[LEN];
static int N;

int main(void)
{
	char input[LEN];
	int i = 0, size;

	puts("Enter a postfix expression");
	fgets(input, sizeof input, stdin);
	size = strlen(input);

	while (i < size)
	{
		if (input[i] == '+')
			push(pop() + pop());
		if (input[i] == '*')
			push(pop() * pop());
		if ((input[i] >= '0') && (input[i] <= '9'))
			push(0);
		while ((input[i] >= '0') && (input[i] <= '9'))
			push(10*pop() + (input[i++]-'0'));
		i++;
	}

	printf("Final value is %d\n", pop());
	return 0;
}

void push(int item)
{ s[N++] = item; }

int pop()
{ return s[--N]; }

Thanks for the reply.

Sorry, I didn't make this clear before, but my input is to take in a single string of equations (in postfix form) with no spaces. I don't think the problem lies with scanf :cry:

Oh, forgive me. I misunderstood. Unfortunately, I can't see how your program would be able to correctly parse an expression with no spaces unless you force a certain number of digits on each operand. As an example, if I wanted "112*" to multiply 11 by 2, how does your program differentiate between that and multiplying 1 by 12?

I think that is a bigger problem than the one you have, which is a failure to separate the digits in your stack. Actually, that problem is a subset of the bigger problem. This line of code illustrates the issue:

push(10*pop() + (input[i++]-'0'));

The statement takes the top of the stack and appends a digit onto the value it finds. The first value is 0, so if I type "21+", 2 would be pushed onto the stack on the first iteration. The second iteration pops 2 and appends 1 to it, making 21, which is then pushed onto the stack.

On the other hand, if you use fgets and separate tokens by whitespace, the code actually does work with the simple expressions I tried. :) I'm sorry to say it, because that seems to diminish the effort you've put into the program already, but I think a redesign of your solution is in order. Perhaps rather than working with individual characters, you can tokenize the expression and process it accordingly:

while (get_token(token))
    {
    if (is_operand(token))
      push(atoi(token));
    else
        {
        if (is_binary(token))
            {
            a = pop();
            b = pop();

            switch (token[0])
                {
                case '+':
                    push(a + b);
                    break;
                case '*':
                    push(a * b);
                    break;
                }
            }
        }
    }

However, allow me to say that what you have already is a rather elegant solution for converting the string representation of a number to its integer equivalent. :)

>Sorry, I didn't make this clear before, but my input is to take in a single string of equations (in postfix form) with no spaces. I don't think the problem lies with scanf.

If you want to handle more than single digit numbers you need to use tokens as eCharisma mentioned. FACT.

However, it complicates matters because instead of pushing and popping single chars from the stack you are having to push and pop bunches of chars, or tokens as they are more commonly known as.

Also,

void push(int);
int pop();

pop() shouldn't return anything. It is customary to have it declared as void. You should have another function, possibly char top() which returns the top value of the stack.

Also it would be a good idea to have your stack prototype declared in a struct.

[IMG]http://img476.imageshack.us/img476/5171/cut20ln.png[/IMG]
Piworld ™
[Tis simple as Pie]

what is the uses of abstract class and interface ? plz tell me where use this concept ?
thank u..........

I forgot to consider double(or more) digit numbers in this stack program.

I also figured out where the problem was and applied a really cheesy way to get around it which uses the atoi function :cry: : because I kinda don't get the conversion this book uses.

int num[2];
num[0] = input[i];
num[1] = '\0';
atoi(num);

As for the token solution, it seems like the best way to go about this sort of problem. Thanks for the tips guys. I wish I saw it sooner. :D

I have another question that's also related to stacks. Suppose I have to use 2 stacks - one for operands (stack 1) and the other for operators (stack 2). So, if I enter a postfix expression (i.e. 598*+) 5, 9, and 8 would go into stack 1 and the operators would go into stack 2. Now, if I wanted to pop an operator from stack 2 and do a calculation with numbers from stack 1 how would I do it? (i.e. 9*8)

Here's what I've come up with (sorry its kinda long):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LEN 100

void initstack(int);
void push(int, int); // second argument is a flag
int pop(int); // argument is a flag

void postfix_to_infix();
void infix_to_postfix();
int convert_num(char *);
void swap();

static int *s1; // stack for numbers
static int *s2; // stack for operators
static int N1; // number stack counter
static int N2; // operator stack counter

int main(void)
{
	char menu;

	puts("1: Infix -> Postfix:");
	puts("2: Postfix -> Infix:");
	scanf("%c", &menu);
	switch(menu)
	{
		case '1': 
			infix_to_postfix();
			break;
		case '2': 
			postfix_to_infix();
			break;
	}
	return 0;	
}
// flag = 0 will do operations on s1
// flag = 1 will do operations on s2
 
void infix_to_postfix()
{
	char input[LEN];
	
	puts("Enter an infix expression:");
	scanf("%s", input);

	int maxN = strlen(input);
	initstack(maxN);

	int i = 0;
	while (i < maxN)
	{
		if (input[i] == '*' || input[i] == '+')
			push(input[i], 1);
		if (input[i] >= '0' && input[i] <= '9')
		{
			push(input[i], 0);
			printf("%c", pop(0));
		}
		if (input[i] == ')')
			printf("%c", pop(1));
		i++;
	}
	puts("");
}

void postfix_to_infix()
{
	char input[LEN];
	char num[2];
	
	puts("Enter a postfix expression:");
	scanf("%s", input);

	int maxN = strlen(input);
	initstack(maxN);

	int i = 0;
	while (i < maxN)
	{
		if (input[i] == '*')
		{
			push(input[i], 1);
			push(pop(0) * pop(0), 0);
		}
		if (input[i] == '+')
		{
			push(input[i], 1);
			push(pop(0) + pop(0), 0);
		}
		if (input[i] >= '0' && input[i] <= '9')
		{
			num[0] = input[i];
			push(convert_num(num), 0);
		}
		i++;
	}
	printf("%d\n", pop(0));
}

void initstack(int maxN)
{ 
	s1 = (int *)malloc(maxN*sizeof(int));
	s2 = (int *)malloc(maxN*sizeof(int));
}

void push(int item, int flag)
{
	if (flag == 0)
		s1[N1++] = item; 
	else
		s2[N2++] = item;
}

int pop(int flag)
{ 
	if (flag == 0)
		return s1[--N1];
	else 
		return s2[--N2];
}

int convert_num(char *num)
{
	num[1] = '\0'; 
	return atoi(num); 
}

void swap()
{
	int t, j = N1;
	t = s1[j-1];
	s1[j-1] = s1[j-2];
	s1[j-2] = t;
}

>I have another question that's also related to stacks. Suppose I have to use 2 stacks - one for operands (stack 1) and the other for operators (stack 2).


Oh dear. You do not need two stacks. The entire postfix expression should be held in one stack only.

For example if your postfix expression was:

23+41+*

You would go through the stack as soon as you encounter an operator you would pop the first three chars out:

pop +
pop 3 
pop 2

Then you would work out the math

3 + 2 = 5

Now you would push the 5 onto the stack

541+*

You would go through the stack again as soon as you encounter an operator you would pop the first three chars out:

pop +
pop 1
pop 4

Then you would work out the math

1 + 4 = 5

Now you would push the 5 onto the stack

55*

You would go through the stack again as soon as you encounter an operator you would pop the first three chars out:

pop *
pop 5
pop 5

Then you would work out the math

5 * 5 = 25

If you haven't already researched what Reverse Polish Notation, then I urge you to do so.

[IMG]http://img476.imageshack.us/img476/5171/cut20ln.png[/IMG]
Piworld ™
[Tis simple as Pie]

I understand the the Postfix notation and the stack concept.

It's just that this problem is asking me to use a stack of operators o_O for some reason that I shall figure out later....

And here's the token implementation xD

token = strtok(input, delim);
	while (token != NULL)
	{
		if ((*token >= '0') && (*token <= '9'))
			push(atoi(token));
		else
		{
			switch(*token)
			{
				case '*': 
					push(pop() * pop());
					break;
				case '+':
					push(pop() + pop());
					break;
			}
		}
		token = strtok(NULL, delim);
	}

>It's just that this problem is asking me to use a stack of operators o_O for some reason

If you are being explicitly asked to create two stacks, one for the operators and another for the numbers, then there must be a logical explanation as to why you have to do it that way. At this moment in time I can't see how that would simplify things me thinks.

Here's a sample program which accepts one digit numbers using only one stack. hmm?

postfix.c

#include <stdio.h>
#include <stdlib.h>


#define MAXSTACK 100
#define EMPTYSTACK -1


void push( char );
char pop();
int empty();
int full();
int convert_num(char);
char convert_char(int);
int operator_s(char);
int do_math(char,char,char);


int top = EMPTYSTACK;
char items[MAXSTACK];


void push(char c) {
   items[++top] = c;
}

char pop() {
   return items[top--];
}

int full()  {
   return top+1 == MAXSTACK;
}

int empty()  {
   return top == EMPTYSTACK;
}

int convert_num(char crap)
{
     int numbers[]={1,2,3,4,5,6,7,8,9};
     char characters[]={"123456789"};
     
     int shite;
     int i;
     for(i = 0; i <  9; i++)
     {
           if(crap==characters[i])
           {
               shite = numbers [i];
           }
     } 
     return shite;
}

char convert_char(int num)
{
         int numbers[] = {1,2,3,4,5,6,7,8,9};
     char characters[] = {"123456789"};
     
     char shite;
     int i;
     for(i = 0; i <  9; i++)
     {
           if( num == numbers[i] )
           {
               shite = characters [i];
           }
     } 
     return shite;
}

int operator_s(char ch)
{
   if ((ch=='+')||(ch=='*')||(ch=='-')||(ch=='/'))
      
      return 1;
   else
      return 0;
}

int do_math(char a,char b,char c)
{
    
    int k,m;
    k = convert_num(b);
    m = convert_num(c);
    
     if (a=='+')
     {
       return k+m;   
     } 
     else if (a=='-')
     {
        return k-m;
     } 
     else if (a=='*')
     {
        return k*m;
     } 
     else if (a=='/')
     {
        return k/m;
     }   
}       
     

int main() {

   char stuff[100];
   char ch;
   int count = 0;
   puts("Please enter your postfix expression, no spaces");
   while ((ch = getchar())!= '\n')
   
   if (!full())
   {
         stuff[count] = ch;
         push(ch);
         count++;
   }
      //printf("%d",count);
      int i;
      char foo;
      int bar;
      for( i=0; i<count; i++)
      {
        if(operator_s(stuff[i])==0)
        {
          //push numbers onto the stack
          push(stuff[i]);
        }
       
        else if(operator_s(stuff[i])==1)
        {
          push(stuff[i]); //push operator onto stack                         
          
          int j;
          char a,b,c;
          
          a = pop();
          b = pop();
          c = pop();
          
          bar = do_math(a,b,c); 
          foo = convert_char(bar); //convert to char
          push(foo);
          //printf("%d ",o);
          
        }
        
      }
      printf("%d",bar);
   
 
   printf("\n");
   getchar();
   return 0;
}

[IMG]http://img476.imageshack.us/img476/5171/cut20ln.png[/IMG]
Piworld ™
[Tis simple as Pie]

This article has been dead for over six months. Start a new discussion instead.