How to find wrong infix expression?

Question

I have to convert infix expression to postfix. My Infix to Postfix code is working without any error. But I have to also find the wrong infix expression. How to solve this problem?

Here is my code : ( I have used my custom stack file)

#include <iostream>
#include <string>
#include "stacktype.cpp"
using namespace std;

string infixToPostFix(string infix);
int higherPrecedenceValidate(char op1, char op2);
int getPrecedence(char op);
int evaluatePostFix(string postfix);

int main()
{
    string infix,postfix;
    int result;
    cin >> infix;
    postfix = infixToPostFix(infix);
    cout << postfix <<endl;
    result = evaluatePostFix(postfix);
    cout << "result: " << result << endl; 

}


string infixToPostFix(string infix){
    StackType<char> operators;
    string postfix;
    for(int i = 0; i < infix.size(); i++){
        // Checking Operator
        if(infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/'){
            while (!operators.IsEmpty() && higherPrecedenceValidate(operators.Top(),infix[i]))
            {
                postfix = postfix + operators.Top();
                operators.Pop();
            }
            operators.Push(infix[i]);

        }
        // Checking Operand
        else if(infix[i] >= '0' && infix[i] <= '9')
        {
            postfix = postfix + infix[i];

        }
        //Checking open bracket
        else if(infix[i] == '(' ){
            operators.Push(infix[i]);
        }

        //Checking closing bracket
        else if(infix[i] == ')' ){
            while (!operators.IsEmpty() && operators.Top() != '(')
            {
                postfix = postfix + operators.Top();
                operators.Pop();
            }
            // poping the opening bracket
            operators.Pop();
        }


    }
    // poping rest of element from the stack..
    while (!operators.IsEmpty())
    {
        postfix = postfix + operators.Top();
        operators.Pop();
    }
    return postfix;
}

int evaluatePostFix(string postfix){
    StackType<int> finalNumbers;
    for(int i = 0; i < postfix.size(); i++){
        // Checking Operator
        if(postfix[i] == '+' || postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/'){
            int resultOfTwoNumber;
            int number2 = finalNumbers.Top();
            finalNumbers.Pop();
            int number1 = finalNumbers.Top();
            finalNumbers.Pop();
            switch (postfix[i])
            {
                case '+':
                    resultOfTwoNumber = number1 + number2;
                    break;
                case '-':
                    resultOfTwoNumber = number1 - number2;
                    break;
                case '*':
                    resultOfTwoNumber = number1 * number2;
                    break;
                case '/':
                    resultOfTwoNumber = number1 / number2;
                    break;
            }
            finalNumbers.Push(resultOfTwoNumber);

        }
        // Checking Operand
        else if(postfix[i] >= '0' && postfix[i] <= '9')
        {
            finalNumbers.Push(postfix[i] - '0');

        }
    }
    return finalNumbers.Top();
}


int higherPrecedenceValidate(char operator1, char operator2)
{
    int op1 = getPrecedence(operator1);
    int op2 = getPrecedence(operator2);
    if(op1 == op2)
        return true;
    return op1 > op2 ?  true: false;
}

int getPrecedence(char op)
{
    int weight = 0;
    switch(op)
    {
    case '+':
    case '-':
        weight = 1;
        break;
    case '*':
    case '/':
        weight = 2;
        break;
    }
    return weight;
}

Now I solved this problem. Here is my wrong infix expression checking code with infix to postfix and postfix to result evalution :

#include <iostream>
#include <string>
#include "stacktype.cpp"
using namespace std;

string infixToPostFix(string infix);
int higherPrecedenceValidate(char op1, char op2);
int getPrecedence(char op);
int evaluatePostFix(string postfix);

int main()
{
    string infix,postfix;
    int result;
    cout << "Infix: ";
    cin >> infix;
    postfix = infixToPostFix(infix);
    cout << "\nPostfix: " << postfix << endl << endl;
    if(postfix != "Wrong Expression"){
        result = evaluatePostFix(postfix);
        cout << "Result: " << result << endl << endl; 
    }


}


string infixToPostFix(string infix){
    StackType<char> operators;
    bool isMathOperatorRepeated = false;
    bool isOperaendRepeated = false;
    string postfix;
    for(int i = 0; i < infix.size(); i++){
        // Checking Operator
        if(infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/'){
            if(isMathOperatorRepeated){
                postfix = "Wrong Expression";

                /* 
                After this for loop there is while loop
                which is checking rest of the char and add it with postfix string .
                So this pushed char should be pop out 
                beacuse infix expression is wrong.
                */

                while (!operators.IsEmpty())
                {
                    operators.Pop();
                }
                break;
            }
            while (!operators.IsEmpty() && higherPrecedenceValidate(operators.Top(),infix[i]))
            {
                postfix = postfix + operators.Top();
                operators.Pop();
            }
            operators.Push(infix[i]);
            isMathOperatorRepeated = true;
            isOperaendRepeated = false;

        }
        // Checking Operand
        else if(infix[i] >= '0' && infix[i] <= '9')
        {
            if(isOperaendRepeated){
                postfix = "Wrong Expression";

                /* 
                After this for loop there is while loop
                which is checking rest of the char and add it with postfix string .
                So this pushed char should be pop out 
                beacuse infix expression is wrong.
                */

                while (!operators.IsEmpty())
                {
                    operators.Pop();
                }
                break;
            }
            postfix = postfix + infix[i];
            isMathOperatorRepeated = false;
            isOperaendRepeated = true;

        }
        //Checking open bracket
        else if(infix[i] == '(' ){
            operators.Push(infix[i]);
            isMathOperatorRepeated = false;
            isOperaendRepeated = false;
        }

        //Checking closing bracket
        else if(infix[i] == ')' ){

            while (!operators.IsEmpty() && operators.Top() != '(')
            {
                postfix = postfix + operators.Top();
                operators.Pop();
            }

            /*
            checking stack beacuse we know 
            that if the infix char is ')'  
            and the stack is empty then the infix expression is wrong

            */
            if(operators.IsEmpty()){
                postfix = "Wrong Expression";
                break;

            }
            else{
                operators.Pop();
            }
            // poping the opening bracket
            isMathOperatorRepeated = false;
            isOperaendRepeated = false;
        }

        // checking that infix expression has invalid char
        else{
            postfix = "Wrong Expression";

            /* 
                After this for loop there is while loop
                which is checking rest of the char in stack.
                So this pushed char should be pop out 
                beacuse infix expression is wrong.
            */
            while (!operators.IsEmpty())
            {
                operators.Pop();
            }
            break;
        }


    }
    // poping rest of element from the stack..
    while (!operators.IsEmpty())
    {
        if(operators.Top() == '('){
            postfix = "Wrong Expression";
            break;
        }
        else{
            postfix = postfix + operators.Top();
            operators.Pop();
        }
    }
    return postfix;
}

int evaluatePostFix(string postfix){
    StackType<int> finalNumbers;
    for(int i = 0; i < postfix.size(); i++){
        // Checking Operator
        if(postfix[i] == '+' || postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/'){
            int resultOfTwoNumber;
            int number2 = finalNumbers.Top();
            finalNumbers.Pop();
            int number1 = finalNumbers.Top();
            finalNumbers.Pop();
            switch (postfix[i])
            {
                case '+':
                    resultOfTwoNumber = number1 + number2;
                    break;
                case '-':
                    resultOfTwoNumber = number1 - number2;
                    break;
                case '*':
                    resultOfTwoNumber = number1 * number2;
                    break;
                case '/':
                    resultOfTwoNumber = number1 / number2;
                    break;
            }
            finalNumbers.Push(resultOfTwoNumber);

        }
        // Checking Operand
        else if(postfix[i] >= '0' && postfix[i] <= '9')
        {
            finalNumbers.Push(postfix[i] - '0');

        }
    }
    return finalNumbers.Top();
}


int higherPrecedenceValidate(char operator1, char operator2)
{
    int op1 = getPrecedence(operator1);
    int op2 = getPrecedence(operator2);
    if(op1 == op2)
        return true;
    return op1 > op2 ?  true: false;
}

int getPrecedence(char op)
{
    int weight = 0;
    switch(op)
    {
    case '+':
    case '-':
        weight = 1;
        break;
    case '*':
    case '/':
        weight = 2;
        break;
    }
    return weight;
}

Answer 1

There are several things below that you should check as you do the conversion to decide if the infix expression is valid:

• Add the final else to the chain determining the character type, i.e. an operator, a digit, or a parenthesis. Your code would hit that branch when the character is not recognized, meaning that the infix expression is invalid. You may need to add another "valid" branch to allow whitespace.
• Add a check to see that an operator is preceded by another operator, as in 2 + * 3. You can do it with a bool flag set in the "this is an operator" branch, and reset everywhere else.
• Add a check that the stack is not empty before popping the opening bracket. The while loop above it can end for two reasons - the stack gets empty, or you find the corresponding opening parenthesis. If the loop ends because the stack is empty, the expression segment has more closing parentheses than opening parentheses, and the expression is invalid.
• Add a check that none of the operators you pop during the final "unwinding" of the stack is a parenthesis. If you find a parenthesis on the stack at the end, the expression has more opening parenthesis than closing parenthesis, hence it is invalid.

When you detect that the expression is invalid, throw an exception, or return a special string to indicate that the conversion has failed.