{"id":894,"date":"2025-11-21T09:00:56","date_gmt":"2025-11-21T03:30:56","guid":{"rendered":"https:\/\/codexplained.in\/?p=894"},"modified":"2025-11-21T09:00:56","modified_gmt":"2025-11-21T03:30:56","slug":"evaluation-of-prefix-expression","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=894","title":{"rendered":"Evaluation Of Prefix Expression"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n#include <ctype.h>\n#include <string.h>\n\n#define MAX 100\n\n\/\/ Stack implementation\ntypedef struct \n{\n    int data[MAX];\n    int top;\n} Stack;\n\n\/\/ Function to initialize the stack\nvoid initStack(Stack *s) \n{\n    s->top = -1;\n}\n\n\/\/ Function to check if the stack is empty\nint isEmpty(Stack *s) \n{\n    return s->top == -1;\n}\n\n\/\/ Function to push an element into the stack\nvoid push(Stack *s, int value) \n{\n    if (s->top == MAX - 1) \n{\n        printf("Stack Overflow\\n");\n        return;\n    }\n    s->data[++(s->top)] = value;\n}\n\n\/\/ Function to pop an element from the stack\nint pop(Stack *s) \n{\n    if (isEmpty(s)) \n{\n        printf("Stack Underflow\\n");\n        return -1;\n    }\n    return s->data[(s->top)--];\n}\n\n\/\/ Function to evaluate a prefix expression\nint evaluatePrefix(char *exp) \n{\n    Stack s;\n    initStack(&s);\n\n    int i = strlen(exp) - 1;\n\n    \/\/ Scan the prefix expression from right to left\n    while (i >= 0) \n{\n        \/\/ Skip spaces\n        if (exp[i] == ' ') \n{\n            i--;\n            continue;\n        }\n\n        \/\/ If the character is an operand (digit)\n        if (isdigit(exp[i])) \n{\n            int num = 0, base = 1;\n\n            \/\/ There could be multiple digits, so we build the number\n            while (i >= 0 && isdigit(exp[i])) \n{\n                num = num + (exp[i] - '0') * base;\n                base *= 10;\n                i--;\n            }\n            \/\/ Push the number onto the stack\n            push(&s, num);\n        }\n\n        \/\/ If the character is an operator\n        else {\n            int operand1 = pop(&s);\n            int operand2 = pop(&s);\n\n            switch (exp[i]) \n{\n                case '+':\n                    push(&s, operand1 + operand2);\n                    break;\n                case '-':\n                    push(&s, operand1 - operand2);\n                    break;\n                case '*':\n                    push(&s, operand1 * operand2);\n                    break;\n                case '\/':\n                    if (operand2 != 0)\n                        push(&s, operand1 \/ operand2);\n                    else\n                        printf("Division by zero error\\n");\n                    break;\n                default:\n                    printf("Invalid operator\\n");\n                    return -1;\n            }\n            i--;\n        }\n    }\n\n    \/\/ The result will be the last element in the stack\n    return pop(&s);\n}\n\nint main() \n{\n    char prefixExp[MAX];\n\n    printf("Enter a valid prefix expression: ");\n    fgets(prefixExp, MAX, stdin);\n\n    \/\/ Evaluate the prefix expression\n    int result = evaluatePrefix(prefixExp);\n\n    printf("The result of the prefix expression is: %d\\n", result);\n    return 0;\n}\n<\/pre><\/div>\n\n\n
Explanation<\/h3>\n\n\n\n
    \n
  1. Prefix Expression<\/strong>: In prefix notation, the operator is placed before its operands. For example, the expression + 9 * 2 6<\/code> is equivalent to (9 + (2 * 6))<\/code> in infix notation.<\/li>\n\n\n\n
  2. Stack Data Structure<\/strong>: We use a stack to evaluate the expression. The key idea is to traverse the expression from right to left, push operands onto the stack, and whenever an operator is encountered, pop the required number of operands from the stack, apply the operator, and push the result back onto the stack.<\/li>\n\n\n\n
  3. Digits Handling<\/strong>: Since prefix expressions can contain multi-digit numbers, we handle them by constructing the number digit by digit, starting from the least significant digit.<\/li>\n\n\n\n
  4. Operators<\/strong>: When encountering an operator, we pop two operands from the stack, apply the operator, and push the result back onto the stack.<\/li>\n\n\n\n
  5. Result<\/strong>: Once the entire expression is processed, the result is the only value remaining in the stack.<\/li>\n<\/ol>\n\n\n\n
    Sample Input and Output<\/strong><\/p>\n\n\n
    \nEnter a valid prefix expression: + 9 * 2 6\nThe result of the prefix expression is: 21\n\n<\/pre><\/div>\n\n\n
    Here, the expression + 9 * 2 6<\/code> translates to 9 + (2 * 6)<\/code> in infix, which equals 21<\/code>. The program correctly evaluates this.<\/p>\n\n\n\n
    How the Program Works:<\/h3>\n\n\n\n
      \n
    • The program reads the prefix expression from the user.<\/li>\n\n\n\n
    • It then processes the expression by pushing operands to the stack and applying operators to the top two operands on the stack.<\/li>\n\n\n\n
    • Finally, it prints the result of the evaluated prefix expression.<\/li>\n<\/ul>\n\n\n\n
      This approach ensures correct evaluation by leveraging the stack data structure to reverse the order of operations as required by the prefix notation.<\/p>\n