Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

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 `‘*’`

.

```
{
"expression": "{(1+2)*3}+4"
}
```

Output:

```
1
```

The mathematical expression as well as the parentheses are valid.

```
{
"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.

- 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`

.

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.

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).

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).

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).

```
/*
* 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:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

Note: Input and Output will already be taken care of.

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 `‘*’`

.

```
{
"expression": "{(1+2)*3}+4"
}
```

Output:

```
1
```

The mathematical expression as well as the parentheses are valid.

```
{
"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.

- 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`

.

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.

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).

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).

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).

```
/*
* 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:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart

- Designed by 500 FAANG+ experts
- Live training and mock interviews
- 17000+ tech professionals trained

00

Days

:

00

Hrs

:

00

Mins

:

00

Secs