How to check if inputted parentheses are valid

Question

Is there an efficient method to find out if a string input uses correctly?

So, "((()))()" is correct. "()()(" is incorrect. "hi())(" is incorrect.

I have tried this:

def valid_parentheses(string): 
    utilList = [] for i in string:     
        utilList.append(i)
    open = utilList.count("(")
    close = utilList.count(")")
    if (open + close) % 2 == 0:
        return True
    else:
        return False

you can recursively\iteratively look for and replace `'()'` with `''` and see if the string you'll end up with is blank — Ma0, Jun 20 '17 at 16:16
Possible duplicate of [Python program to check matching of simple parentheses](https://stackoverflow.com/questions/38833819/python-program-to-check-matching-of-simple-parentheses) — Bill the Lizard, Jun 20 '17 at 16:17

score 1 · Answer 1 · answered Jun 20 '17 at 16:18

1

You can just loop through your text and keep count. +1 for (, -1 for ). At the end of the loop, the counter should be 0. If the counter ever goes negative, you can exit early knowing that they are not balanced.

answered Jun 20 '17 at 16:18

Bill the Lizard

398,270
210
566
880

"hi())(" would add to 0, but the final use of ")(" is incorrect. – Enesxg Jun 20 '17 at 16:22
@Enesxg You'd exit early at the second `)` in that example, because the counter would be -1. – Bill the Lizard Jun 20 '17 at 16:23
Thanks, Bill the Lizard – Enesxg Jun 20 '17 at 16:27
Do you have an idea what you would do to check for the " [ ] { } " braces as well? – Enesxg Jun 21 '17 at 14:59
@Enesxg I'd do the same thing. Just set up separate counters for each kind of braces. – Bill the Lizard Jun 21 '17 at 19:07

score 0 · Answer 2 · answered Jun 20 '17 at 16:19

0

Use a variable to track the parentheses nesting level. It starts at 0.

Iterate through the string. Each time you reach an open parenthesis, add 1 the nesting level. Subtract 1 each time you reach a closing parenthesis.

If the number is ever negative, or if the number is not zero when you reach the end of the string, then the parentheses are malformed.

answered Jun 20 '17 at 16:19

Michael Stroud

279
1
2

"hi())(" would add to 0, but the final use of ")(" is incorrect. – Enesxg Jun 20 '17 at 16:23

How to check if inputted parentheses are valid

2 Answers2