Question

: In this assignment you will write a C++ program that evaluates an arithmetic expression (represented with an infix notation), then outputs this expression in prefix form and also outputs the result of the calculation. The program will first convert the input infix expression to a prefix expression (using the Stack ADT) and then calculate the result (again, using the Stack ADT). The details are provided in the following sections.

Answer 1

The code below will convert an infix expression to postfix and evaluate the postfix expression.

To convert an infix to prefix the following steps will takes place;

1) Reverse the infix expression i.e A+B*C will become C*B+A. Note while reversing each ‘(‘ will become ‘)’ and each ‘)’   becomes ‘(‘.

2) Obtain the postfix expression of the modified expression i.e CB*A+.

3) Reverse the postfix expression. Hence in the example prefix is +A*BC.

The code below will convert a infix to prefix and evaluate the prefix:

Try this code with any other expressions, Note that only enter single digit expressions(0.....9).

//program to convert infix to prefix and evaluate prefix 
#include <bits/stdc++.h> 
using namespace std; 

//function to checking for operator
bool isOperator(char c) 
{ 
        return (!isalpha(c) && !isdigit(c)); 
} 

//function to get the priority between operators
int getPriority(char C) 
{ 
        if (C == '-' || C == '+') 
                return 1; 
        else if (C == '*' || C == '/') 
                return 2; 
        else if (C == '^') 
                return 3; 
        return 0; 
} 

//function for converting infix to postfix
string infixToPostfix(string infix) 
{ 
        infix = '(' + infix + ')'; 
        int l = infix.size(); 
        stack<char> char_stack; 
        string output; 

        for (int i = 0; i < l; i++) { 
                // If the scanned character is an operand, add it to output
                if (isalpha(infix[i]) || isdigit(infix[i])) 
                        output += infix[i]; 

                // If the scanned character is an ‘(‘, push it to the stack
                else if (infix[i] == '(') 
                        char_stack.push('('); 

                // If the scanned character is an ‘)’, pop and output from the stack until an ‘(‘ is encountered. 
                else if (infix[i] == ')') { 
                        while (char_stack.top() != '(') { 
                                output += char_stack.top(); 
                                char_stack.pop(); 
                        } 
                        // Remove '(' from the stack 
                        char_stack.pop(); 
                } 

                // Operator found 
                else { 
                        if (isOperator(char_stack.top())) { 
                                while (getPriority(infix[i]) 
                                <= getPriority(char_stack.top())) { 
                                        output += char_stack.top(); 
                                        char_stack.pop(); 
                                } 
                                // Push current Operator on stack 
                                char_stack.push(infix[i]); 
                        } 
                } 
        } 
        return output; 
} 

string infixToPrefix(string infix) 
{ 
        int l = infix.size(); 
        // Reverse infix 
        reverse(infix.begin(), infix.end()); 
        // Replace ( with ) and vice versa 
        for (int i = 0; i < l; i++) { 
                if (infix[i] == '(') { 
                        infix[i] = ')'; 
                        i++; 
                } 
                else if (infix[i] == ')') { 
                        infix[i] = '('; 
                        i++; 
                } 
        } 
    //get postfix
        string prefix = infixToPostfix(infix); 
        // Reverse postfix 
        reverse(prefix.begin(), prefix.end()); 

        return prefix; 
} 

/**Evaluation of Prefix **/
bool isOperand(char c) 
{ 
    // If the character is a digit then it must be an operand 
    return isdigit(c); 
} 
  
double evaluatePrefix(string exprsn) 
{ 
    stack<double> Stack; 
    for (int j = exprsn.size() - 1; j >= 0; j--) { 
        // Push operand to Stack 
        if (isOperand(exprsn[j])) 
        // To convert exprsn[j] to digit subtract '0' from exprsn[j].
            Stack.push(exprsn[j] - '0'); 
  
        else { 
            // Operator encountered; Pop two elements from Stack 
            double o1 = Stack.top(); 
            Stack.pop(); 
            double o2 = Stack.top(); 
            Stack.pop(); 
  
            // Use switch case to operate on o1 and o2 and perform o1 O o2. 
            switch (exprsn[j]) { 
            case '+': 
                Stack.push(o1 + o2); 
                break; 
            case '-': 
                Stack.push(o1 - o2); 
                break; 
            case '*': 
                Stack.push(o1 * o2); 
                break; 
            case '/': 
                Stack.push(o1 / o2); 
                break; 
            } 
        } 
    } 
    return Stack.top(); 
} 

// main code 
int main() 
{ 
    //string to store expression(infix)
        string s = ("9*8-4");
        string p;     //string to store expression(prefix)
        cout << "Orginal Expression: " << s << std::endl;
        p = infixToPrefix(s);    //calling infix to prefix convert
        cout << "Prefix Notation: " <<p << std::endl;
        //calling prefix evaluation and printing reusult
        cout << "Evaluation result of prefix: " << evaluatePrefix(p) << std::endl; 
        return 0; 
} 

OUTPUT: