Question

Stacks are used by compilers to help in the process of evaluating expressions and generating machine language code.In this exercise, we investigate how compilers evaluate arithmetic expressions consisting only of constants, operators and parentheses. Humans generally write expressions like 3 + 4and 7 / 9in which the operator (+ or / here) is written between its operands—this is called infix notation. Computers “prefer” postfix notation in which the operator is written to the right of its two operands. The preceding infix expressions would appear in postfix notation as 3 4 +and 7 9 / respectively. To evaluate a complex infix expression, a compiler would first convert the expression to post-fix notation, and then evaluate the postfix version of the expression. Each of these algorithms requires only a single left-to-right pass of the expression. Each algorithm uses a stack in support of its operation, and in each the stack is used for a different purpose. In this exercise, you’ll write a version of the infix-to-postfix conversion algorithm. Write a program that converts an ordinary infix arithmetic expression (assume a valid expression is entered) with single digit integers such as (6 + 2) * 5 -8 / 4 to a postfix expression. The postfix version of the preceding infix expression is 6 2 + 5 * 8 4 / - The program should read the expression into character array infix and use modified versions of the stack functions you have implemented so farto help create the postfix expression in character array postfix. The algorithm for creating a postfix expression is as follows: 1. Push a left parenthesis '(' onto the stack. 2. Append a right parenthesis ')' to the end of infix. 3. While the stack is not empty, read infix from left to right and do the following: 3.1. If the current character in infix is a digit, copy it to the next element of postfix. 3.2. If the current character in infix is a left parenthesis, push it onto the stack. 3.3. If the current character in infix is an operator, 3.3.1. Pop operators (if there are any) at the top of the stack while they have equal or higher precedence than the current operator and insert the popped operators in postfix. 3.3.2. Push the current character in infix onto the stack. 3.4. If the current character in infix is a right parenthesis 3.4.1. Pop operators from the top of the stack and insert them in postfix until a left parenthesis is at the top of the stack. 3.4.2. Pop (and discard) the left parenthesis from the stack. The following arithmetic operations are allowed in an expression: + addition - subtraction * multiplication / division ^ exponentiation % remainder The stack should be maintained with the following declarations: struct stackNode { char data; struct stackNode *nextPtr; }; typedef struct stackNode StackNode; typedef StackNode *StackNodePtr; The program should consist of main and eight other functions with the following function headers: void convertToPostfix( char infix[], char postfix[] ) Convert the infix expression to postfix notation. int isOperator( char c ) Determine if c is an operator. int precedence( char operator1, char operator2 ) Determine if the precedence of operator1 is less than, equal to, or greater than the precedence of operator2. The function returns -1, 0 and 1, respectively. void push( StackNodePtr *topPtr, char value ) Push a value on the stack. char pop( StackNodePtr *topPtr ) Pop a value off the stack. char stackTop( StackNodePtr topPtr ) Return the top value of the stack without popping the stack. int isEmpty( StackNodePtr topPtr ) Determine if the stack is empty. void printStack( StackNodePtr topPtr ) Print the stack.

The following arithmetic operations are allowed in an expression: + addition subtraction * multiplication / division exponentiation $tacks are used by compilers to help in the process of evaluating expressions and generating machine language sedelo this exercise, we investigate how compilers evaluate arithmetic expressions consisting only of constants, operators and parentheses. Humans generally write expressions like 3 + 4and 7 / 9in which the operator (+ or / here) is written between its operands-this is called infix notation. Computers "prefer" postfix notation in which the operator written to the right of its two operands. The preceding infix expressions would appear in postfix notation as 3 4 +and 7 9 / respectively. To evaluate a complex infix expression, a compiler would first convert the expression to post-fix notation, and then evaluate the postfix version of the expression. Each of these algorithms requires only a single left-to-right pass of the expression. Each algorithm uses a stack in support of its operation, and in each the stack is used for a different purpose. In this exercise, you'll write a version of the infix-to-postfix conversion algorithm. Write a program that converts an ordinary infix arithmetic expression (assume a valid expression is entered) with single digit integers such as (6+2) 5-8/4 to a postfix expression. The postfix version of the preceding infix expression is 6 2 +5 * 84/- The program should read the expression into character array infix and use modified versions of the stack functions you have implemented so far to help create the postfix expression character array postfix. The algorithm for creating a postfix expression is as follows: % remainder The stack should be maintained with the following declarations: struct staskNode. char data; struct stackNode. *next tG }; typedef struct stack Node Stackade 1. Push a left parenthesis 'l' onto the stack. 2. Append a right parenthesis')' to the end of infix. typedef Stack Nade StackNodefta The program should consist of main and eight other functions with the following function headers: 3. While the stack is not empty, read infix from left to right and do the following: void seosesttafestfix char infix[], char postfix[] ) 3.1. If the current character in infix is a digit, copy it to the next element of postfix. Convert the infix expression to postfix notation 3.2. If the current character in infix is a left parenthesis, push it onto the stack. int isOperator charc) 3.3. If the current character in infix is an operator, Determine if c is an operator 3.3.1. Pop operators (if there are any) at the top of the stack while they have equal or higher precedence than int precedencel char operator1, char operator2) the current operator and insert the popped operators in postfix. Determine if the precedence of operator1 is less than, equal to, or greater than the precedence of operator2. 3.3.2. Push the current character in infix onto the stack The function returns -1,0 and 1, respectively 3.4. If the current character in infix is a right parenthesis void push Stack Node Ptstoppt, char value) 3.4.1. Pop operators from the top of the stack and insert them in postfix until a left parenthesis is at the top Push a value on the stack. of the stack char papl StackNedetr "tretc) Pop a value off the stack. 3.4.2. Pop (and discard) the left parenthesis from the stack. char stackter StackNedett teretc) Return the top value of the stack without popping the stack. int isEmptyl StackNedelt teretc) Determine if the stack is empty void BootStackl StackNedelt terc) Print the stack

Answer 1

Working code implemented in C and appropriate comments provided for better understanding:

Source code for main.c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
typedef struct stackNode StackNode;
typedef StackNode *StackNodePtr;
struct stackNode {
   char data;
   struct stackNode *nextPtr;
};

void convertToPostfix( char infix[], char postfix[] ); //Convert the infix expression to postfix notation.
int isOperator( char c ); //Determine if c is an operator.
int precedence( char operator1, char operator2 );//Determine if the precedence of operator1 is less than, equal to, or greater than the precedence of operator2. The function returns -1, 0 and 1, respectively.
void push( StackNodePtr *topPtr, char value ); //Push a value on the stack.
char pop( StackNodePtr *topPtr ); // Pop a value off the stack.
char stackTop( StackNodePtr topPtr ); //Return the top value of the stack without popping the stack.
int isEmpty( StackNodePtr topPtr ); //Determine if the stack is empty.
void printStack( StackNodePtr topPtr );// print stack

int main(void) {   
   char infix[256]; //initialise empty infix array
   char postfix[256]; //initialise empty postfix array
   printf("Enter an infix expression: ");
   scanf("%s", &infix);
   printf("The original infix expression is: \n");
   printf("%s\n", infix);
   convertToPostfix(infix, postfix);
   printf("The expression in postfix notation is: %s\n",postfix); //answer

}
void convertToPostfix( char infix[], char postfix[] ) {  
   int infixIndex=0; //iterates through infix
   int postfixIndex=0;//iterates through postfix

   StackNodePtr head = NULL; //initialise empty stack
   push(&head, '(');
   printStack(head);
   strcat(infix,")"); //append ")" onto infix
   while(isEmpty(head) == 1) { //stack not empty
       if(isdigit(infix[infixIndex])){ //is digit
           postfix[postfixIndex++] = infix[infixIndex++];
       }
       if(infix[infixIndex]=='(') { //is "("
           push(&head, infix[infixIndex++]);
           printStack(head);
       }
     
       if(isOperator(infix[infixIndex])==1) {//is ^,/,*,%,+,-
           while((isOperator(stackTop(head)) == 1) && ((precedence(stackTop(head), infix[infixIndex]) != -1))) { //is operator with higher precedence than current infix value
               postfix[postfixIndex++] = pop(&head); //insert operator in postfix  
           }
           push(&head ,infix[infixIndex++]);
           printStack(head);
       }
       if(infix[infixIndex]==')') { //is ")"
           infixIndex++;
           while(stackTop(head) != '(') {
               postfix[postfixIndex++] = pop(&head);
               printStack(head);
           }
           pop(&head);
           printStack(head);
       }
   }
}

int isEmpty(StackNodePtr topPtr) {
   if(topPtr == NULL){
       return 0; // empty, return 0
   }else{
       return 1; //not empty
   }
}
void push (StackNodePtr *topPtr, char value) {
   StackNodePtr snp;
   snp = malloc(sizeof(StackNode)); //allocate memory for snp
   if(snp != NULL) { //memory allocation succeeded
   snp->data = value;
   snp->nextPtr = *topPtr;
   *topPtr = snp;
   }
  
}
char pop( StackNodePtr *topPtr ) {
   StackNodePtr snp = *topPtr;
   char data = snp->data;
   *topPtr = (*topPtr)->nextPtr; //move topPtr to new top
   free(snp);
   return data;
}
int isOperator(char c) {
   if(c=='+' || c=='-' || c=='*' || c=='/' || c=='^' || c=='%') {
       return 1; //is operator
   }
   return -1; //is not an operator
}
int precedence(char operator1, char operator2) {
   //precedence: ^ < / <= *<= % < + <= -
   if(operator1 == '+' || operator1 == '-'){ //compare + and -, they equal precedence
       if(operator2 == '+' || operator2 == '-'){
           return 0;      
       }else{
           return -1;      
       }
   }else if(operator1 == '*' || operator1 == '/' || operator1 == '%'){ //compare * , / and %, they equal precedence
       if(operator2 == '+' || operator2 == '-'){
           return 1;      
       }else if(operator2 == '*' || operator2 == '/' || operator2 == '%'){
           return -0;      
       }else{
           return -1;      
       }
   }else if(operator1 == '^'){ //^ has the greatest precedence
       if(operator2 == '^'){
           return 0;  
       }else{
           return 1;      
       }
   }
}
char stackTop( StackNodePtr topPtr ) {
   if(topPtr != NULL){
       return topPtr -> data; //peek at top
   }
}
void printStack( StackNodePtr topPtr ) {
   while(topPtr != NULL) {
       printf("%c\t", topPtr->data);
       topPtr=topPtr->nextPtr; //update topPtr
   }
   printf("NULL \n");

}

Sample Output Screenshots:

X C C ( ( ( >./main Enter an infix expression: (6+2) *5-8/4 The original infix expression is: (6+2) *5-8/4 NULL NULL + NULL NULL NULL NULL NULL / NULL NULL NULL NULL The expression in postfix notation is: 62+5+84/- ( + C C C C

Hope it helps, if you like the answer give it a thumbs up. Thank you.