About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Valid Expression Problem

You have to check whether a given string is a valid mathematical expression or not. A string is considered valid if it contains matching opening and closing parenthesis as well as valid mathematical operations. 

  • Parentheses: (, ), [, ], {, and }
  • Numbers: 0 to 9
  • Operators: +, -, and *

An expression containing only parentheses is considered valid if it contains the correct opening and closing parentheses. For example: “{()}” is considered valid.

Example One:

Input: {(1+2)*3}+4

Output: True

We can clearly see that the above expression mathematical expression and parentheses are valid.

Example Two:

Input: ((1+2)*3*)

Output: False

Here the parentheses are valid, but the mathematical expression is not valid. The operator * does not have an operand.

Notes:

Input Parameters: There is a single argument in the input — a string named expression

Output: Return boolean value “true” if the expression is valid; else, return “false”

Constraints:
  • 1 <= length(expression) <= 100000
  • Characters allowed in the expression string: +, -, * and 0 to 9

Solution (solution.java):

We traverse the string from left to right and maintain two stacks — one for numbers and the other for operators and parentheses. 

When we encounter a number, we push it to the integer stack. Similarly, when we encounter an operator or open bracket, we push it to the character stack. 

When we encounter a closed bracket, we remove characters from the character stack until we encounter the corresponding open parentheses.

Also, when we get an operator, we remove two integers from the integer stack. 

In case we are not able to perform any of the operations, we return “false,” indicating an expression invalid. 

Time Complexity:

O(n), where n denotes the length of the expression string.

As each character of the string enters one of the stacks maximum once and is removed from it maximum once, the complexity of the algorithm is O(n).

Auxiliary Space Used:

O(n), where n denotes the length of the expression string.

We create two stacks for storing the appropriate characters and numbers; so, the auxiliary space used is O(n) + O(n) = O(n).

Space Complexity:

O(n), where n denotes the length of the expression string.

We will require O(n) space to store the input, auxiliary space used is O(n), and O(1) is used to store the output; hence, total complexity is O(n).


 // -------- START --------
    public static boolean is_valid(String expression) {
        boolean result = true;
        /*stores digits*/
        Stack st1 = new Stack<>();
        /*stores operators and parantheses*/
        Stack st2 = new Stack<>();
        boolean isTrue = true;
        for (int i = 0; i < expression.length(); i++) {
            char temp = expression.charAt(i);
            /*if the character is a digit, we push it to st1*/
            if (isDigit(temp)) {
                st1.push(temp - '0');
                if(isTrue) {
                    isTrue = false;
                }
                else {
                    return false;
                }
            } 
            /*if the character is an operator, we push it to st2*/
            else if (isOperator(temp)) {
                st2.push(temp);
                isTrue = true;
            } 
            else {
                /*if the character is an opening parantheses we push it to st2*/
                if(isBracketOpen(temp)) {
                    st2.push(temp);
                } 
                /*If it is a closing bracket*/
                else {
                    boolean flag = true;
                    /*we keep on removing characters until we find the corresponding
                    open bracket or the stack becomes empty*/
                    while (!st2.isEmpty()) {
                        char c = st2.pop();
                        if (c == getCorrespondingChar(temp)) {
                            flag = false;
                            break;
                        } 
                        else {
                            if (st1.size() < 2) {
                                return false;
                            }
                            else {
                                st1.pop();
                            }
                        }
                    }
                    if (flag) {
                        return false;
                    }

                }
            }
        }
        while (!st2.isEmpty()) {
            char c = st2.pop();
            if (!isOperator(c)) {
                return false;
            }
            if (st1.size() < 2) {
                return false;
            }
            else {
                st1.pop();
            }
        }
        if (st1.size() > 1 || !st2.isEmpty()) {
            return false;
        }
        return result;
    }
    /*method to get corresponding opening and closing bracket.*/
    public static char getCorrespondingChar(char c) {
        if (c == ')') {
            return '(';
        }
        else if (c == ']') {
            return '[';
        }
        return '{';
    }

    /*checks if the given bracket is open or not.*/
    public static boolean isBracketOpen(char c) {
        if (c == '(' || c == '[' || c == '{') {
            return true;
        }
        return false;
    }

    /*checks if the given character is a digit.*/
    public static boolean isDigit(char c) {
        if (c >= '0' && c <= '9') {
            return true;
        }
        return false;
    }

    public static boolean isOperator(char c) {
        if (c == '+' || c == '-' || c == '*') {
            return true;
        }
        return false;
    }
    // -------- END --------


Attend our Free Webinar on How to Nail Your Next Technical Interview

Recommended Posts

All Posts