Valid Expression Problem Statement
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. The string contains the following set of parentheses ‘(‘, ’)’, ’[’, ’]’, ’{’, ’}’, numbers from 0 to 9 and following operators ‘+’, ’-’ and ‘*’.
Example One
{
"expression": "{(1+2)*3}+4"
}
Output:
1
The mathematical expression as well as the parentheses are valid.
Example Two
{
"expression": "((1+2)*3*)"
}
Output:
0
Here the parentheses are valid but the mathematical expression is not. There is an operator ‘*’ without any operand after it.
Notes
- An expression that consists of only parentheses is considered valid if it contains correct opening and closing parentheses. Example:
“{()}” is considered valid.
Constraints:
- 1 <=
length of the expression <= 100000
- Possible characters in the expression string:
‘+’, ‘-’, ‘*’ and [0-9]
We have provided one solution.
We will refer to the length of the expression as n.
Valid Expression Solution: Optimal
We traverse the string from left to right and maintain 2 stacks – one for numbers and the other one for operators and parentheses. When we encounter a number we push it to the integer stack and similarly, in case of an operator or an 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 2 integers from the integer stack. In case we are not able to perform any of the operations, we return false, thus considering the expression invalid.
Time Complexity
O(n).
As each character of the string enters one of the stacks at most 1 time and is removed from it at most one time, the complexity of the algorithm turns out to be O(n).
Auxiliary Space Used
O(n).
We create 2 stacks for storing the appropriate characters and numbers respectively, so the auxiliary space used is O(n) + O(n) = O(n).
Space Complexity
O(n).
We will require O(n) space to store input and auxiliary space used is O(n) and O(1) to store output, hence total complexity will be O(n).
Code For Valid Expression Solution: Optimal
/*
* Asymptotic complexity in terms of length of \`expression\` \`n\`:
* Time: O(n).
* Auxiliary space: O(n).
* Total space: O(n).
*/
public static boolean is_valid(String expression) {
boolean result = true;
/*stores digits*/
Stack<Integer> st1 = new Stack<>();
/*stores operators and parantheses*/
Stack<Character> 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;
}
We hope that these solutions to valid parentheses problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.
If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.
Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.
We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:
To learn more, register for the FREE webinar.
.png)
