A program which evaluates a mathematical expression by first converting it into RPN and evaluating the result using precedence of operators

Question

#include <stdio.h>

char infix[200];
char stack[200];
char queue[200];
int count_stack = 0; 
int count_queue = 0;

int precedence(char x)
{
    switch (x)
    {
    case '^':
        return 2;
    case '/':
        return 1;
    case '*':
        return 1;
    case '+':
        return 0;
    case '-':
        return 0;
    }
}
int isChar(char x)
    {
    if (x == '(' || x == ')' || x == '^' || x == '*' || x == '/' || x == '+' || x == '-')
    {
        return 1;
    }
    else
    {
        return 0;
    }
    }

int isNum(char x){
    if (x >= '0' && x <= '9'){
        return 1;
    }
    else{
        return 0; 
    }
}

void pushtoStack(char x){

    if (count_stack >= 200 ) {
        printf("stack over flow");
        return;
    }
    else {
        stack[count_stack] = x;
        count_stack++;
    }
}

void pop()
{
    if (count_stack < 0) {
        printf("stack under flow");
    }
    else {    
        //push to queue
        queue[count_queue] = stack[count_stack];
        count_queue++;
        count_stack--; 
        int i = count_stack; 
        while(i!=0)  
        {  
            stack[i] = stack[i-1]; // assign arr[i-1] to arr[i]
            i--; 
        }
        // return item;
    }
}

void pushToQueue(char x){
    queue[count_queue] = x;
    count_queue++; 
}
int main(){

    scanf("%s", infix);
    int i = 0; 
    while (infix[i] != '\0'){
        if (count_stack==0 && isChar(infix[i]) == 1){
            pushtoStack(infix[i]);
            i++; 
        }
        else if (isNum(infix[i]) == 1){
            pushToQueue(infix[i]);
            i++; 
        }
        else if(count_stack !=0 && infix[i]=='(')
        {
            pushtoStack(infix[i]); 
            i++;
        }
        else if(count_stack !=0 && infix[i]==')')
        {
            int j = count_stack; 
            while(stack[j]!='('){
                pushToQueue(stack[j]);
                count_stack--; 
                j--; 
            }
            pop(infix[i]);
            pop(stack[count_stack]); 
            i++;
        }
        else if (count_stack !=0 && isChar(infix[i]) == 1 && precedence(infix[i]) <= precedence(stack[count_stack]))           
        {
            
            while(precedence(stack[count_stack]) >= precedence(infix[i])){
                pushToQueue(stack[count_stack]);
                count_queue++;
                pop();
                i++; 
            }
            pushtoStack(infix[i]);
            i++;
        }
    }
    

    for (int i = 0; i < 100;i++){
        printf("%c", queue[i]); 
    }
    
}

Trying to do: Storing input in infix, reading chars and storing the postfix in queue. Queue will be evaluated later using precedence rules

Program is stuck after receiving input E.g. 5-6*9 NO OUTPUT (program keeps running)

NOTE: The evaluation of postfix is not included in the code.

This is for an assignment and I am restricted to using only the std lib of C <stdio.h>

If this problem can be solved in some other way, kindly edify me

Answer 1

There are several small errors throughout your code, but one big problem is in the implementation of pop. To pop an item from a LIFO stack, you can just return the item currently at the top of the stack and decrement the stack index. You shouldn't need a while loop to shift any elements because only the top element is actually affected.

stack[--count_stack]

This is exactly what the program does in this section:

/*
  Variable j is unnecessary because it always has exactly the same value as count_stack.
  Just remove variable j and replace stack[j] with stack[count_stack]
 */
int j = count_stack;
while (stack[j] != '(') {
  // pushToQueue and count_stack-- pop the top of the stack.
  pushToQueue(stack[j]);
  count_stack--;
  j--;
}

By pushing the top of the stack to the queue and then decrementing count_stack, the program is essentially popping the top of the stack, but without using a pop function.

Another issue is that later in the program pop is called with an argument, but the pop function definition doesn't define any arguments.

// Function definition has no arguments.
void pop() {
    ...
}

// ...

// Called with an argument.
pop(infix[i]);
pop(stack[count_stack]);

Calling a function with more arguments than it is defined to have is an example of undefined behavior. This means that the C standard doesn't specify how the code should execute and the compiler is allowed to do essentially whatever it chooses. Undefined behavior should be avoided because the result is unpredictable.

It looks like you are trying to implement the Shunting Yard Algorithm. This is the pseudo-code from the Wikipedia article (slightly modified for brevity):

while there are tokens to be read:
    read a token
    if the token is:
    - a number:
        put it into the output queue
    - an operator o1:
        while (
            there is an operator o2 other than "(" at the top
            of the operator stack, and (o2 has greater precedence than o1
            or they have the same precedence and o1 is left-associative)
        ):
            pop o2 from the operator stack into the output queue
        push o1 onto the operator stack
    - "(":
        push it onto the operator stack
    - ")":
        while the operator at the top of the operator stack is not "(":
            {assert the operator stack is not empty}
            /* If the stack runs out without finding a "(", then there are mismatched parentheses. */
            pop the operator from the operator stack into the output queue
        {assert there is a "(" at the top of the operator stack}
        pop the "(" from the operator stack and discard it
/* After the while loop, pop the remaining items from the operator stack into the output queue. */
while there are tokens on the operator stack:
    /* If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. */
    {assert the operator on top of the stack is not a "("}
    pop the operator from the operator stack onto the output queue