13 Replies - 317 Views - Last Post: Yesterday, 06:37 AM Rate Topic: ***-- 2 Votes

#1 Caedmon   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 23-August 19

I am trying to write a C program to evaluate postfix expression.

Posted 08 September 2019 - 12:05 AM

I want to do this by using linked list implementation of stack. I have written a code for the same. The compiler does not find an error in my program but when I run it I don't get any output. I am using a GNU GCC compiler by the way.

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

struct stack{
int data;
struct stack * link;
};

struct stack * top;
int evaluate(char  exp[]);
void push(int x);
int pop();

int main(){
char exp[] = "3 2 * 5 4 * +";
printf("%d",evaluate(exp));
return 0;
}

int evaluate(char  exp[]){
int i;
int len = strlen(exp);
for(i = 0; i<=len;i++){

    if(exp[i]==' '){
        continue;
    }
    else if(isdigit(exp[i])==1){
        int num = 0;
        while(isdigit(exp[i])){
            num = num*10 + (int)(exp[i]-'0');
            i++;
        }
        i--;
        push(num); // Pushing the operand to the stack
    }else{

    int val2 = pop();
    int val1 = pop();

    switch(exp[i]){

            case '+': push(val1 + val2); break;
            case '-': push(val1 - val2); break;
            case '*': push(val1 * val2); break;
            case '/': push(val1/val2); break;

     }

    }

}
return pop();
}
void push(int x){

struct stack * temp = (struct stack *)malloc(sizeof(struct stack));

(*temp).data = x;
(*temp).link = top;
top = temp;
return;
}

int pop(){
struct stack * temp = top;
int ans = (*temp).data;
top = (*temp).link;
return ans;
}



Can you please tell me where I have gone wrong. Much thanks in advance !

Is This A Good Question/Topic? 0
  • +

Replies To: I am trying to write a C program to evaluate postfix expression.

#2 Salem_c   User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 2369
  • View blog
  • Posts: 4,496
  • Joined: 30-May 10

Re: I am trying to write a C program to evaluate postfix expression.

Posted 08 September 2019 - 12:39 AM

A lesson in using the debugger and reading the manual.

When code doesn't work, compile it with the -g flag and use the debugger.
If you're using an IDE, then -g is assumed when you pick "Debug" build.

$ gcc -Wall -Wextra -g foo.c
$ gdb -q ./a.out
Reading symbols from ./a.out...done.
(gdb) run
Starting program: ./a.out 

Program received signal SIGSEGV, Segmentation fault.
0x00000000004007c8 in pop () at foo.c:70
70	int ans = (*temp).data;
(gdb) bt
#0  0x00000000004007c8 in pop () at foo.c:70
#1  0x00000000004006d9 in evaluate (exp=0x7fffffffdde0 "3 2 * 5 4 * +") at foo.c:41
#2  0x0000000000400664 in main () at foo.c:19
(gdb) p temp
$1 = (struct stack *) 0x0
(gdb) list
65	return;
66	}
67	
68	int pop(){
69	struct stack * temp = top;
70	int ans = (*temp).data;
71	top = (*temp).link;
72	return ans;
73	}
74	
(gdb) up
#1  0x00000000004006d9 in evaluate (exp=0x7fffffffdde0 "3 2 * 5 4 * +") at foo.c:41
41	    int val2 = pop();
(gdb) list
36	        }
37	        i--;
38	        push(num); // Pushing the operand to the stack
39	    }else{
40	
41	    int val2 = pop();
42	    int val1 = pop();
43	
44	    switch(exp[i]){
45	
(gdb) info locals
val2 = 4196413
val1 = 0
i = 0
len = 13
(gdb) p isdigit(exp[i])
$2 = 2048


Basically, you called pop() on an empty stack.

Now look at the evaluate() frame, i is zero.
So it's barfed on handling the very first character.


And the manual page.
http://www.cplusplus...cctype/isdigit/

> else if(isdigit(exp[i])==1)

Quote

Return Value
A value different from zero (i.e., true) if indeed c is a decimal digit. Zero (i.e., false) otherwise.

Checking a result is 0 is fine.
Specifically assuming that true is always 1 is bad.
Was This Post Helpful? 0
  • +
  • -

#3 Caedmon   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 23-August 19

Re: I am trying to write a C program to evaluate postfix expression.

Posted 08 September 2019 - 04:11 AM

I rewrote my if statement. I tried to work around the pop() method and calling it but the program is still not giving an output. Would you be kind enough to write the required changes in my code. Thank you.
Was This Post Helpful? 0
  • +
  • -

#4 jimblumberg   User is offline

  • member icon

Reputation: 5745
  • View blog
  • Posts: 17,601
  • Joined: 25-December 09

Re: I am trying to write a C program to evaluate postfix expression.

Posted 08 September 2019 - 04:46 AM

Quote

I rewrote my if statement. I tried to work around the pop() method and calling it but the program is still not giving an output.

Show what you tried, then maybe someone will be able to help further.


Jim
Was This Post Helpful? 0
  • +
  • -

#5 Caedmon   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 23-August 19

Re: I am trying to write a C program to evaluate postfix expression.

Posted 13 September 2019 - 08:16 AM

I worked around the code and changed it. Now I am getting an output but it is wrong. Here is what I did :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

struct Stack{
int top;
unsigned capacity;
int * array;
};

int evaluate(char * exp);
struct Stack * createStack(unsigned capacity);
void push(struct Stack * stack, char op);
int pop(struct Stack * stack);
int isEmpty(struct Stack * stack);

int main(){

char exp[] = "3 2 *";
printf("%d",evaluate(exp));
return 0;
}

int evaluate(char * exp){

struct Stack * stack = createStack(strlen(exp));
if(!stack) return -1;
int i;

for(i = 0;exp[i];++i){

    if(exp[i] == ' ') continue;
    else if(isdigit(exp[i])){
        int num = 0;
        while(isdigit(exp[i])){
            num = num*10 + (int)(exp[i]-'0');
            i++;
        }
        i--;
        push(stack,num);
    }
    else{
        int val2 = pop(stack);
        int val1 = pop(stack);

        switch(exp[i])
        {
         case '+' : push(stack,val1 + val2); break;
         case '-' : push(stack,val1 - val2); break;
         case '*' : push(stack,val1 * val2); break;
         case '/' : push(stack,val1 / val2); break;
        }
    }

}
return pop(stack);
}

struct Stack * createStack(unsigned capacity){

struct Stack * stack = (struct Stack *)malloc(sizeof(struct Stack));

if(!stack) return NULL;

(*stack).top = -1;
(*stack).capacity = capacity;
(*stack).array = (int *)malloc((*stack).capacity * sizeof(int));
if(!(*stack).array) return NULL;

return stack;
}

void push(struct Stack * stack,char op){
(*stack).array[++(*stack).top] = op;
return;
}

int pop(struct Stack * stack){
if(!isEmpty(stack)) return (*stack).array[(*stack).top--];
return '$';
}

int isEmpty(struct Stack * stack){

return (*stack).top == 1;
}


Was This Post Helpful? 0
  • +
  • -

#6 modi123_1   User is online

  • Suitor #2
  • member icon



Reputation: 15215
  • View blog
  • Posts: 60,898
  • Joined: 12-June 08

Re: I am trying to write a C program to evaluate postfix expression.

Posted 13 September 2019 - 08:38 AM

I would highly recommend stepping through your code. I do not believe things are happening as you expect.

Example of inconsistency the 'is empty' checking if top is equal to 1, but the 'create stack' shows an empty stack's top is -1. There's some confusion.
Was This Post Helpful? 0
  • +
  • -

#7 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7020
  • View blog
  • Posts: 23,840
  • Joined: 05-May 12

Re: I am trying to write a C program to evaluate postfix expression.

Posted 13 September 2019 - 08:51 AM

You need to help us out more since we are not sitting right there beside you and looking at your screen. You say that output is wrong. What output are you getting? What output were you expecting to see? What inputs did you give your program?

Also, as an aside, decide whether you are writing C code or C++ code. If you are writing C code, then there is no need to cast the pointer returned by malloc(). For example:
struct Stack * stack = (struct Stack *)malloc(sizeof(struct Stack));


should be written as:
struct Stack * stack = malloc(sizeof(struct Stack));


In C++, you would have to perform that cast.
Was This Post Helpful? 0
  • +
  • -

#8 jimblumberg   User is offline

  • member icon

Reputation: 5745
  • View blog
  • Posts: 17,601
  • Joined: 25-December 09

Re: I am trying to write a C program to evaluate postfix expression.

Posted 13 September 2019 - 09:04 AM

Quote

In C++, you would have to perform that cast.

No, in C++ you should be using smart pointers or new/delete.

@Caedmon you really need to learn to properly indent your code so that it is easier to read.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

struct Stack
{
    int top;
    unsigned capacity;
    int * array;
};

int evaluate(char * exp);
struct Stack * createStack(unsigned capacity);
void push(struct Stack * stack, char op);
int pop(struct Stack * stack);
int isEmpty(struct Stack * stack);

int main()
{

    char exp[] = "3 2 *";
    printf("%d",evaluate(exp));
    return 0;
}

int evaluate(char * exp)
{

    struct Stack * stack = createStack(strlen(exp));
    if(!stack) return -1;
    int i;

    for(i = 0; exp[i]; ++i)
    {

        if(exp[i] == ' ') continue;
        else if(isdigit(exp[i]))
        {
            int num = 0;
            while(isdigit(exp[i]))
            {
                num = num*10 + (int)(exp[i]-'0');
                i++;
            }
            i--;
            push(stack,num);
        }
        else
        {
            int val2 = pop(stack);
            int val1 = pop(stack);

            switch(exp[i])
            {
                case '+' :
                    push(stack,val1 + val2);
                    break;
                case '-' :
                    push(stack,val1 - val2);
                    break;
                case '*' :
                    push(stack,val1 * val2);
                    break;
                case '/' :
                    push(stack,val1 / val2);
                    break;
            }
        }

    }
    return pop(stack);
}

struct Stack * createStack(unsigned capacity)
{

    struct Stack * stack = (struct Stack *)malloc(sizeof(struct Stack));

    if(!stack) return NULL;

    (*stack).top = -1;
    (*stack).capacity = capacity;
    (*stack).array = (int *)malloc((*stack).capacity * sizeof(int));
    if(!(*stack).array) return NULL;

    return stack;
}

void push(struct Stack * stack,char op)
{
    (*stack).array[++(*stack).top] = op;
    return;
}

int pop(struct Stack * stack)
{
    if(!isEmpty(stack)) return (*stack).array[(*stack).top--];
    return '$';
}

int isEmpty(struct Stack * stack)
{

    return (*stack).top == 1;
}





Jim
Was This Post Helpful? 1
  • +
  • -

#9 Caedmon   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 23-August 19

Re: I am trying to write a C program to evaluate postfix expression.

Posted 13 September 2019 - 09:40 AM

I am getting an output of 16. But I am expecting to get an output of 6 because the answer of 3 2 * is 6.
Was This Post Helpful? 0
  • +
  • -

#10 jimblumberg   User is offline

  • member icon

Reputation: 5745
  • View blog
  • Posts: 17,601
  • Joined: 25-December 09

Re: I am trying to write a C program to evaluate postfix expression.

Posted 13 September 2019 - 10:50 AM

Did you run the program with your debugger? Set a breakpoint early in main() and single step through the program watching the values of your variables as you step. You may want to break some of your compound lines down into the individual parts as well, for example (a very simple example):
    //return pop(stack);
    int ret_value = pop(stack);
    return ret_value;



Also be careful about implicit casts, your array is an array of int so what happens if you try to push a char onto your stack?

It appears that you may be pushing and popping incorrect values to and from your stack. You may want to create a function that you can use to easily examine the contents of your stack. In some places you appear to be pushing a char into your stack, but you seem to be popping ints off the stack. You need to decide which one you should be using.

Have you tried getting this to work without all the pointers? Why are you trying to allocate "stack" dynamically? You should be able to use a single instance of your stack instead. Also you may want to try getting the program working using a statically allocated array instead of using a dynamically allocated array. Using a single "normal" instance of your stack with a "normal" statically allocated array should be much easier to debug. After you get the "normal" instances working properly you can later add the mess of the dynamic allocated array.

Jim
Was This Post Helpful? 0
  • +
  • -

#11 Caedmon   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 23-August 19

Re: I am trying to write a C program to evaluate postfix expression.

Posted 13 September 2019 - 12:07 PM

Thank you very much.
My problem is resolved.
I was, as jimblumberg pointed, I was pushing and popping elements of the wrong datatype. I changed my array to char type and pushed and popped char elements.
Also as modi123_1 pointed, the isEmpty function was returning 1 when it was supposed to return -1 if the stack was empty.
Thank you again
Was This Post Helpful? 0
  • +
  • -

#12 jimblumberg   User is offline

  • member icon

Reputation: 5745
  • View blog
  • Posts: 17,601
  • Joined: 25-December 09

Re: I am trying to write a C program to evaluate postfix expression.

Posted 13 September 2019 - 12:16 PM

Quote

I changed my array to char type and pushed and popped char elements.

Okay, but what happens if the value being pushed is larger than what a char can hold? For example char exp[] = "133 2 *"?

Jim
Was This Post Helpful? 0
  • +
  • -

#13 Caedmon   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 23-August 19

Re: I am trying to write a C program to evaluate postfix expression.

Posted Yesterday, 06:16 AM

I did not think of this shortcoming with pushing and popping char elements into char array. If I take your expression i.e
char exp[] = "133 2" , I get 0 as the output but the desired output is 256.
However, if I use int array and push elements by typecasting them to int then I can work with larger numbers as well.
Thanks for bringing this to my notice.
Was This Post Helpful? 0
  • +
  • -

#14 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7020
  • View blog
  • Posts: 23,840
  • Joined: 05-May 12

Re: I am trying to write a C program to evaluate postfix expression.

Posted Yesterday, 06:37 AM

But you shouldn't have to do any type casting as you push values into your stack. You just need to make the variable you are using to accumulate the value of each operands be the appropriate type.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1