Consider our implementation of the program that evaluates an arithmetic expressi

Question

Consider our implementation of the program that evaluates an arithmetic expression using "Postfix" notation using a "Stack". There are a few flaws that should be addressed. You can use pseudo-code or make changes to the existing code to implement the following: 1) It may be the case that the expression is invalid, so an attempt to calculate the answer would result in disaster. The application should include a routine to check the expression and indicate to the user, e.g., through an error code, if the expression is invalid. What should the code look for to make sure that an expression is valid? 2) For our MyStack class we created methods emptyCheck() which returns True if the stack becomes empty; top(), that returns the value of the top element in the stack; push(a1) that places the value of a1 onto the top of the stack; and pop() that removes the top element of the stack, if any. To process any stack, you may only use those routines and some primitive data variables to temporarily store a value or two. If necessary, you can temporarily create a second stack to store values. a) Design a method in MyStack called getBottomValue() that returns the values at the bottom of the stack b) Design a method in MyStack called stackStack(MyStack T) that pushes the values from stack T, in the correct order. When the routine is done, the top element in the ("this") stack should be the top element from T. T should also be restored to its original condition. Illustration: 2 4 The ("this") Stack T Stack 4 Resulting "this" Stack

Explanation / Answer

Solution:

The below code is used to check the validity of the expression in the infix to postfix conversion code:

if (exp[i] == ')')
        {
            while (!isEmpty(stack) && peek(stack) != '(')
                postFix[++k] = pop(stack);
            if (!isEmpty(stack) && peek(stack) != '(')
                return ; // invalid expression              
            else
                pop(stack);
        }

Complete code for reference:

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

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

// Stack Operations
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;
}
int isEmpty(struct Stack* stack)
{
    return stack->top == -1 ;
}
char peek(struct Stack* stack)
{
    return stack->array[stack->top];
}
char pop(struct Stack* stack)
{
    if (!isEmpty(stack))
        return stack->array[stack->top--] ;
    return '$';
}
void push(struct Stack* stack, char op)
{
    stack->array[++stack->top] = op;
}


// A utility function to check if the given character is operand
int isOperand(char ch)
{
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}

// A utility function to return precedence of a given operator
// Higher returned value means higher precedence
int Prec(char ch)
{
    switch (ch)
    {
    case '+':
    case '-':
        return 1;

    case '*':
    case '/':
        return 2;

    case '^':
        return 3;
    }
    return -1;
}

extern void toPostFix(char *,char *);

int main(void) {

    char convertedstring2[255];
    char convertedstring1[255],checkstring1[255],checkstring2[255];
    char string1[255]="A*B+(C*D)+E";
    char string2[255]="(A+B)*(C+D)+E";

    toPostFix(string1,convertedstring1);
    printf(" String 1- Infix to Postfix is %s ",convertedstring1);

    toPostFix(string2,convertedstring2);
    printf(" String 2- Infix to Postfix is %s ",convertedstring2);
        
  
    return EXIT_SUCCESS;
}

void toPostFix(char *exp,char *postFix){
  
   int i, k;

    // Create a stack of capacity equal to expression size
    struct Stack* stack = createStack(strlen(exp));
    if(!stack) // See if stack was created successfully
        return ;

    for (i = 0, k = -1; exp[i]; ++i)
    {
         // If the scanned character is an operand, add it to output.
        if (isOperand(exp[i]))
            postFix[++k] = exp[i];
       
        // If the scanned character is an ‘(‘, push it to the stack.
        else if (exp[i] == '(')
            push(stack, exp[i]);
      
        // If the scanned character is an ‘)’, pop and output from the stack
        // until an ‘(‘ is encountered.
        else if (exp[i] == ')')
        {
            while (!isEmpty(stack) && peek(stack) != '(')
                postFix[++k] = pop(stack);
            if (!isEmpty(stack) && peek(stack) != '(')
                return ; // invalid expression              
            else
                pop(stack);
        }
        else // an operator is encountered
        {
            while (!isEmpty(stack) && Prec(exp[i]) <= Prec(peek(stack)))
                postFix[++k] = pop(stack);
            push(stack, exp[i]);
        }

    }

    // pop all the operators from the stack
    while (!isEmpty(stack))
        postFix[++k] = pop(stack );

    postFix[++k] = '';
  
}

/*

Output:

String 1- Infix to Postfix is AB*CD*+E+

String 2- Infix to Postfix is AB+CD+*E+

*/

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.