{"id":988,"date":"2025-11-21T09:01:08","date_gmt":"2025-11-21T03:31:08","guid":{"rendered":"https:\/\/codexplained.in\/?p=988"},"modified":"2025-11-21T09:01:08","modified_gmt":"2025-11-21T03:31:08","slug":"convert-infix-expression-to-prefix","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=988","title":{"rendered":"Convert Infix Expression to Prefix"},"content":{"rendered":"\n

Steps for converting Infix to Prefix<\/strong><\/p>\n\n\n\n

    \n
  1. Reverse the infix expression.<\/strong><\/li>\n\n\n\n
  2. Replace (<\/code> with )<\/code> and vice versa<\/strong>.<\/li>\n\n\n\n
  3. Convert the modified expression to postfix<\/strong> using the same algorithm you would use for infix to postfix conversion.<\/li>\n\n\n\n
  4. Reverse the postfix expression<\/strong> to get the prefix expression.<\/li>\n<\/ol>\n\n\n\n

    Let’s break these steps down further:<\/p>\n\n\n\n

      \n
    • Step 1<\/strong>: Reversing the infix expression.\n
        \n
      • Example: If the infix is A + B * C<\/code>, after reversing, it becomes C * B + A<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • Step 2<\/strong>: Swap (<\/code> and )<\/code>.\n
          \n
        • If the original expression has parentheses, you’ll need to swap them. This doesn’t apply to our example, but if it did, you’d reverse parentheses.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Step 3<\/strong>: Convert the reversed expression to postfix.\n
            \n
          • Use the standard algorithm for converting an infix expression to postfix:\n
              \n
            • If the symbol is an operand, add it to the result.<\/li>\n\n\n\n
            • If the symbol is an operator, pop operators from the stack that have greater or equal precedence, then push the current operator.<\/li>\n\n\n\n
            • If it’s a parenthesis, handle it appropriately (push (<\/code> to the stack, and pop when encountering )<\/code>).<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • Step 4<\/strong>: Reverse the resulting postfix expression to get the prefix expression.<\/li>\n<\/ul>\n\n\n\n

              Precedence and Associativity Rules:<\/h3>\n\n\n\n
                \n
              • Operators like +<\/code> and -<\/code> have lower precedence compared to *<\/code> and \/<\/code>.<\/li>\n\n\n\n
              • If operators have the same precedence, associativity (left-to-right or right-to-left) comes into play.<\/li>\n<\/ul>\n\n\n\n

                Program Implementation in C:<\/h3>\n\n\n\n

                Steps for converting Infix to Prefix:<\/h3>\n\n\n\n
                  \n
                1. Reverse the infix expression.<\/strong><\/li>\n\n\n\n
                2. Replace (<\/code> with )<\/code> and vice versa<\/strong>.<\/li>\n\n\n\n
                3. Convert the modified expression to postfix<\/strong> using the same algorithm you would use for infix to postfix conversion.<\/li>\n\n\n\n
                4. Reverse the postfix expression<\/strong> to get the prefix expression.<\/li>\n<\/ol>\n\n\n\n

                  Let’s break these steps down further:<\/p>\n\n\n\n

                    \n
                  • Step 1<\/strong>: Reversing the infix expression.\n
                      \n
                    • Example: If the infix is A + B * C<\/code>, after reversing, it becomes C * B + A<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                    • Step 2<\/strong>: Swap (<\/code> and )<\/code>.\n
                        \n
                      • If the original expression has parentheses, you’ll need to swap them. This doesn’t apply to our example, but if it did, you’d reverse parentheses.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                      • Step 3<\/strong>: Convert the reversed expression to postfix.\n
                          \n
                        • Use the standard algorithm for converting an infix expression to postfix:\n
                            \n
                          • If the symbol is an operand, add it to the result.<\/li>\n\n\n\n
                          • If the symbol is an operator, pop operators from the stack that have greater or equal precedence, then push the current operator.<\/li>\n\n\n\n
                          • If it’s a parenthesis, handle it appropriately (push (<\/code> to the stack, and pop when encountering )<\/code>).<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                          • Step 4<\/strong>: Reverse the resulting postfix expression to get the prefix expression.<\/li>\n<\/ul>\n\n\n\n

                            Precedence and Associativity Rules:<\/h3>\n\n\n\n
                              \n
                            • Operators like +<\/code> and -<\/code> have lower precedence compared to *<\/code> and \/<\/code>.<\/li>\n\n\n\n
                            • If operators have the same precedence, associativity (left-to-right or right-to-left) comes into play.<\/li>\n<\/ul>\n\n\n\n

                              Program Implementation in C:<\/h3>\n\n\n
                              \n#include<stdio.h>\n#include<string.h>\n#include<ctype.h>\n\n#define MAX 100\n\n\/\/ Stack structure\nstruct Stack {\n    int top;\n    char items[MAX];\n};\n\nvoid push(struct Stack *s, char item) \n{\n    if (s->top == MAX - 1) \n{\n        printf("Stack Overflow\\n");\n        return;\n    }\n    s->items[++(s->top)] = item;\n}\n\nchar pop(struct Stack *s) \n{\n    if (s->top == -1) \n{\n        printf("Stack Underflow\\n");\n        return '\\0';\n    }\n    return s->items[(s->top)--];\n}\n\nchar peek(struct Stack *s) \n{\n    return s->items[s->top];\n}\n\nint isEmpty(struct Stack *s) \n{\n    return s->top == -1;\n}\n\n\/\/ Function to check if the character is an operator\nint is Operator(char ch) \n{\n    return (ch == '+' || ch == '-' || ch == '*' || ch == '\/' || ch == '^');\n}\n\n\/\/ Function to get precedence of the operators\nint precedence(char op) \n{\n    switch (op) \n{\n        case '+':\n        case '-':\n            return 1;\n        case '*':\n        case '\/':\n            return 2;\n        case '^':\n            return 3;\n        default:\n            return 0;\n    }\n}\n\n\/\/ Function to reverse the string\nvoid reverse(char *exp) \n{\n    int len = strlen(exp);\n    for (int i = 0; i < len \/ 2; i++) \n{\n        char temp = exp[i];\n        exp[i] = exp[len - i - 1];\n        exp[len - i - 1] = temp;\n    }\n}\n\n\/\/ Function to convert infix to postfix\nvoid infixToPostfix(char *exp, char *result) \n{\n    struct Stack stack;\n    stack.top = -1;\n    int k = 0;\n\n    for (int i = 0; exp[i]; i++) \n{\n        \/\/ If the scanned character is an operand, add it to the result\n        if (is a l num(exp[i])) \n{\n            result[k++] = exp[i];\n        }\n        \/\/ If the scanned character is '(', push it to the stack\n        else if (exp[i] == '(')\n{\n            push(&stack, exp[i]);\n        }\n        \/\/ If the scanned character is ')', pop and add to result until '(' is encountered\n        else if (exp[i] == ')') \n{\n            while (!is Empty(&stack) && peek(&stack) != '(') \n{\n                result[k++] = pop(&stack);\n            }\n            pop(&stack); \/\/ Remove '(' from stack\n        }\n        \/\/ If the scanned character is an operator\n        else if (is Operator(exp[i])) \n{\n            while (!is Empty(&stack) && precedence(peek(&stack)) >= precedence(exp[i])) \n{\n                result[k++] = pop(&stack);\n            }\n            push(&stack, exp[i]);\n        }\n    }\n\n    \/\/ Pop all the operators from the stack\n    while (!is  Empty(&stack)) \n{\n        result[k++] = pop(&stack);\n    }\n    result[k] = '\\0'; \/\/ Null-terminate the result string\n}\n\n\/\/ Function to convert infix to prefix\nvoid infix To Prefix(char *exp, char *result) \n{\n    int len = str len(exp);\n\n    \/\/ Step 1: Reverse the infix expression\n    reverse(exp);\n\n    \/\/ Step 2: Replace '(' with ')' and vice versa\n    for (int i = 0; i < len; i++) \n{\n        if (exp[i] == '(')\n            exp[i] = ')';\n        else if (exp[i] == ')')\n            exp[i] = '(';\n    }\n\n    \/\/ Step 3: Convert the modified infix expression to postfix\n    infix To Postfix(exp, result);\n\n    \/\/ Step 4: Reverse the postfix expression to get the prefix expression\n    reverse(result);\n}\n\nint main() \n{\n    char infix[MAX], prefix[MAX];\n\n    printf("Enter an infix expression: ");\n    gets(infix); \/\/ Read the infix expression\n\n    infix To Prefix(infix, prefix);\n\n    printf("Prefix expression: %s\\n", prefix);\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
                              Explanation of the Code:<\/h3>\n\n\n\n
                                \n
                              • Stack Operations<\/strong>: The stack operations (push, pop, and peek) are used to manage operators while converting the expression.<\/li>\n\n\n\n
                              • Precedence<\/strong>: The precedence()<\/code> function returns the precedence of operators. Higher numbers indicate higher precedence.<\/li>\n\n\n\n
                              • Reversing and Conversion<\/strong>: The main function infixToPrefix()<\/code> handles reversing the infix expression and calling the infixToPostfix()<\/code> function, which uses the stack to convert the expression.<\/li>\n\n\n\n
                              • Final Reversal<\/strong>: After converting to postfix, the result is reversed to get the final prefix expression.<\/li>\n<\/ul>\n\n\n\n
                                Example Input and Output:<\/h3>\n\n\n
                                \nInput: A + B * C\nOutput: +A*BC\n\nInput: (A - B) * (C + D)\nOutput: *-AB+CD\n<\/pre><\/div>\n\n\n
                                Detailed Explanation:<\/h3>\n\n\n\n
                                  \n
                                1. The user enters an infix expression like A + B * C<\/code>.<\/li>\n\n\n\n
                                2. The program reverses it to C * B + A<\/code>.<\/li>\n\n\n\n
                                3. Then it converts this reversed expression to postfix (CB*A+<\/code>).<\/li>\n\n\n\n
                                4. Finally, it reverses the postfix result to get the prefix expression +A*BC<\/code>.<\/li>\n<\/ol>\n\n\n\n
                                  This program efficiently converts any valid infix expression to its corresponding prefix notation using stack operations and string manipulation techniques.<\/p>\n