{"id":891,"date":"2025-11-21T08:54:13","date_gmt":"2025-11-21T03:24:13","guid":{"rendered":"https:\/\/codexplained.in\/?p=891"},"modified":"2025-11-21T08:54:13","modified_gmt":"2025-11-21T03:24:13","slug":"convert-infix-expression-to-postfix","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=891","title":{"rendered":"Convert Infix Expression to Postfix"},"content":{"rendered":"\n

Problem Overview:<\/h3>\n\n\n\n

Infix Expression:<\/strong> The expression where operators are placed between operands. For example: A + B<\/code>.<\/p>\n\n\n\n

Postfix Expression (also called Reverse Polish Notation):<\/strong> The operators are placed after their operands. For example: A B +<\/code>.<\/p>\n\n\n\n

Steps to Convert Infix to Postfix:<\/h3>\n\n\n\n
    \n
  1. Use a stack<\/strong> to store operators until they are needed.<\/li>\n\n\n\n
  2. Operands (like A, B, etc.) are directly added<\/strong> to the postfix output.<\/li>\n\n\n\n
  3. Operators are pushed to the stack<\/strong> but can only be popped when they follow the precedence and associativity rules.<\/li>\n\n\n\n
  4. Parentheses:<\/strong> Opening parentheses (<\/code> are pushed to the stack, and when a closing parenthesis )<\/code> is encountered, the stack is popped to the output until the corresponding (<\/code> is found.<\/li>\n<\/ol>\n\n\n\n

    Precedence Rules:<\/h3>\n\n\n\n
      \n
    • +<\/code> and -<\/code> have the same precedence (low).<\/li>\n\n\n\n
    • *<\/code>, \/<\/code>, and %<\/code> have the same precedence (higher than +<\/code> and -<\/code>).<\/li>\n\n\n\n
    • ^<\/code> (exponentiation) has the highest precedence.<\/li>\n\n\n\n
    • Associativity of ^<\/code> is right-to-left, while the others are left-to-right.<\/li>\n<\/ul>\n\n\n\n

      Now, let\u2019s write a C program based on this logic.<\/p>\n\n\n

      \n#include <stdio.h>\n#include <ctype.h>  \/\/ for isdigit() function\n#include <stdlib.h> \/\/ for exit() function\n\n#define MAX 100  \/\/ maximum size of the stack\n\n\/\/ Stack structure\nchar stack[MAX];\nint top = -1;  \/\/ initialize stack top pointer\n\n\/\/ Function to push elements onto the stack\nvoid push(char c) \n{\n    if (top == (MAX - 1))\n\n {\n        printf("Stack Overflow\\n");\n        exit(1);  \/\/ terminate the program\n    }\n    stack[++top] = c;\n}\n\n\/\/ Function to pop elements from the stack\nchar pop() {\n    if (top == -1)\n{\n        printf("Stack Underflow\\n");\n        exit(1);\n    }\n    return stack[top--];\n}\n\n\/\/ Function to check precedence of operators\nint precedence(char symbol) \n{\n    switch (symbol) \n{\n        case '+':\n        case '-':\n            return 1;\n        case '*':\n        case '\/':\n        case '%':\n            return 2;\n        case '^':\n            return 3;\n        default:\n            return 0;\n    }\n}\n\n\/\/ Function to determine if it's an operator\nint isOperator(char symbol) \n{\n    return (symbol == '+' || symbol == '-' || symbol == '*' || symbol == '\/' || symbol == '^' || symbol == '%');\n}\n\n\/\/ Function to convert infix to postfix\nvoid infixToPostfix(char infix[]) \n{\n    char postfix[MAX];  \/\/ result string for postfix\n    int i = 0, j = 0;   \/\/ i for infix, j for postfix\n\n    while (infix[i] != '\\0') \n{\n        char current = infix[i];\n\n        \/\/ If the current character is an operand, add it to postfix\n        if (isalnum(current)) \n{\n            postfix[j++] = current;\n        }\n        \/\/ If the current character is '(', push it to the stack\n        else if (current == '(') \n{\n            push(current);\n        }\n        \/\/ If the current character is ')', pop until '(' is found\n        else if (current == ')') \n{\n            while (top != -1 && stack[top] != '(') \n{\n                postfix[j++] = pop();\n            }\n            pop();  \/\/ remove '(' from the stack\n        }\n        \/\/ If the current character is an operator\n        else if (isOperator(current)) \n{\n            while (top != -1 && precedence(stack[top]) >= precedence(current)) \n{\n                postfix[j++] = pop();\n            }\n            push(current);  \/\/ push current operator to stack\n        }\n\n        i++;\n    }\n\n    \/\/ Pop all remaining operators from the stack\n    while (top != -1) \n{\n        postfix[j++] = pop();\n    }\n\n    postfix[j] = '\\0';  \/\/ null-terminate the postfix string\n    printf("Postfix Expression: %s\\n", postfix);\n}\n\n\/\/ Main function to drive the program\nint main() \n{\n    char infix[MAX];\n\n    printf("Enter an Infix Expression: ");\n    scanf("%s", infix);\n\n    infixToPostfix(infix);  \/\/ Call the conversion function\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
      Explanation of the Code:<\/h3>\n\n\n\n
        \n
      1. Stack Operations<\/strong>:\n
          \n
        • push()<\/code> adds an operator or parenthesis to the stack.<\/li>\n\n\n\n
        • pop()<\/code> removes and returns the top element from the stack.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Operator Precedence<\/strong>:\n
            \n
          • The precedence()<\/code> function assigns priority to operators (^<\/code> has the highest, then * \/ %<\/code>, and finally + -<\/code>).<\/li>\n<\/ul>\n<\/li>\n\n\n\n
          • Main Conversion Logic<\/strong>:\n
              \n
            • Loop through each character in the infix expression:\n
                \n
              • If the character is an operand (letter or digit), it’s directly added to the output (postfix).<\/li>\n\n\n\n
              • If it\u2019s an opening parenthesis (<\/code>, it\u2019s pushed to the stack.<\/li>\n\n\n\n
              • If it\u2019s a closing parenthesis )<\/code>, we pop from the stack to the output until an opening parenthesis is encountered.<\/li>\n\n\n\n
              • If it\u2019s an operator, we pop operators from the stack to the output while their precedence is higher than or equal to the current operator.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
              • After the loop ends, any remaining operators in the stack are popped and added to the output.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                Sample Output<\/strong><\/p>\n\n\n
                \nEnter an Infix Expression: A+B*C\nPostfix Expression: ABC*+\n\n<\/pre><\/div>\n\n\n
                Key Notes:<\/h3>\n\n\n\n
                  \n
                • Parentheses help override operator precedence. For example, in (A+B)*C<\/code>, the addition is done before multiplication.<\/li>\n\n\n\n
                • Without parentheses, the normal precedence of operators will apply.<\/li>\n<\/ul>\n\n\n\n
                  This program demonstrates how to correctly convert an infix expression to a postfix expression using stack operations in C language.<\/p>\n\n\n\n
                  <\/p>\n