Question

Total point: 15

Introduction: For this assignment you have to write a c program that will take an infix expression as input and display the postfix expression of the input. After converting the postfix expression, the program should evaluate the expression from the postfix and display the result.

What should you submit?

Write all the code in a single file and upload the .c file.

Problem

We as humans write math expression in infix notation, e.g. 5 + 2 (the operators are written in-between the operands). In computer’s language however, it is preferred to have the operators on the right side of the operands, i.e. 5 2 +. For more complex expressions that include parenthesis and multiple operators, a compiler has to convert the expression into postfix first and then evaluate the resulting postfix.

Write a program that takes an “infix” expression as input, uses stacks to convert it into postfix expression, and finally evaluates it. It must support the following operations:

+ - / * ^ % (

Example

Infix expression:

(7 – 3) / (2 + 2)

Postfix expression:

7 3 - 2 2 + /

Result: 1

Rubric:

1. If code does not compile: 0

1. Checking the balance of the parenthesis: 2 point

1. Incorrect postfix expression per test case: -2 points

1. Correct postfix but incorrect value per test case: -1 points

1. Handling single digit inputs: maximum 13 point

1. Handling two-digit inputs: 100 percent (if pass all test cases)

Some hints (but it is not the only way):

1. You will need to use stacks in three places

1. One for parenthesis check [char stack]
2. One during infix to postfix [char stack]

1. One during evaluation [int stack]

For a and b above, you can use same array and same push, pop method as both of them are char. But for evaluation you have int stack and you might consider to create another push pop method to handle it. Maybe push_int, pop_int, etc.

1. You can create a function for obtaining operator priority. It should take an operator as input and return its precedence as an integer.

1. During evaluation you will need to convert char into integer. Example for single digit: char c = '5';

int x = c - '0';

Answer 1

Program Screenshot:

Sample output:

Code to copy:

#include <stdio.h>
#include <ctype.h>
//define the size of the stack as 50
#define SIZE 50
//declare a character array
//and assign the top value with -1 globally.
char stack[SIZE];
int top = -1;

//definition of the function
//it removes the space in the given string
void removeSpaces(char* data)
{
   //define char pointers
   char* temp1 = data;
   char* temp2 = data;
   //iterate the loop and remove the spaces
   while (*temp2 != 0)
   {
       *temp1 = *temp2++;
       if (*temp1 != ' ')
           temp1++;
   }
   *temp1 = 0;
}

//definition of the function push()
void push(char item)
{
   //increment the top values
   //and store the item in the stack
   stack[++top] = item;
}

//definition of the function pop()
char pop()
{
   //decrement the get value of
   //stack at top and decrement the top value
   return (stack[top--]);
}

//definition of the function getPrecedence()
//takes a character and return its precedence values
int getPrecedence(char ch)
{
   switch (ch)
   {
   case '#':
       return 0;
   case '(':
       return 1;
   case '+':
   case '-':
       return 2;
   case '*':
   case '/':
       return 3;
   }
}

//definition of the function convertToPostfix()
//convert the infix string to postfix string
void convertToPostfix(char *infix, char *postfix)
{
   //declare the variables
   char ch, item;
   int i = 0, j = 0;
   //call the function to remove
   //the space in the infix string
   removeSpaces(infix);
   // call push() to insert '#' into the stack
   push('#');
   //iterate the each character of the infix string.
   while ((ch = infix[i++]) != '\n')
   {
       //if the character is open brace
       //push the character into the stack
       if (ch == '(')
       {
           push(ch);
       }
       //if the character is alphanumeric
       else if (isalnum(ch))
       {
           //assign the character to postfix string
           postfix[j] = ch;
           j++;
           postfix[j] = ' ';
           j++;
       }
       //if the character is closed brace
       //pop the character from the stack
       //assign the character to postfix string
       //until open brace occur
       else if (ch == ')')
       {
           while (stack[top] != '(')
           {
               postfix[j] = pop();
               j++;
               postfix[j] = ' ';
               j++;
           }  
           //pop the value from the stack
           item = pop();
       }
       else
       {
           //call getPrecedence() and check the precedence
           //of ch and the top value of stack
           while (getPrecedence(stack[top]) >= getPrecedence(ch))
           {
               //pop the character from the stack
               //assign the character to postfix string
               postfix[j] = pop();
               j++;
               postfix[j] = ' ';
               j++;
           }
           //push the character into the stack
           push(ch);
       }
   }
   //pop the character from the stack and push into
   //the postfix until end of the stack.
   while (stack[top] != '#')
   {
       postfix[j] = pop();
       j++;
       postfix[j] =' ';
       j++;
      
   }
   postfix[j] = 0;
}

//definition of the function evaluatePostfix
//evaluates and returns the value of postfix.
int evaluatePostfix(char *postfix)
{
   //declare the variables.
   int i = 0, value1, value2;
   char ch;

   while ((ch = postfix[i++]) != 0)
   {
       if (ch != ' ')
       {
           //if the character is digit,
           //convert into character and push into stack
           if (isdigit(ch))
           {
               push(ch - '0');
           }
           else
           {
               //pop two values from the stack
               value2 = pop();
               value1 = pop();
               //depends on the character,
               //find the result of the opration.
               //and push into the stack.
               switch (ch)
               {
               case '+': push(value1 + value2);
                   break;
               case '-': push(value1 - value2);
                   break;
               case '*': push(value1*value2);
                   break;
               case '/': push(value1 / value2);
                   break;
               case ' ':
                   break;
               }
           }
       }
      
   }
   //return the top value of the stack.
   return stack[top];
}
int main()
{
   //declare the variables
   char infix[50], postfix[50];
   //prompt and read the infix expression
   printf("Infix expression: ");
   fgets(infix, 50, stdin);
   //convert into postfix
   convertToPostfix(infix, postfix);
   //print the postfix expression
   printf("\nPostfix Expression: %s", postfix);
   //make top as -1.
   top = -1;
   //print the result.
   printf("\n\nResult of evaluation of postfix expression: %d\n", evaluatePostfix(postfix));
   return 0;
}