Determining a string's structure

Question

I have a program that displays square brackets, '[' and ']'. It displays them in random order and a random amount of times (up to 99).

The code below is my current code, it displays things like the following each time you run the module.

Input:

[[[[]]]]
[][]][]][[][]
[]]]][[[[[[]]][][][[]

My code:

import random
import string

def randomGen(N):
    return random.randint(1,N)

char1 = '['
char2 = ']'
finalist = []
newList = []
newList2 = []

newValue = randomGen(99)
newValue2 = randomGen(99)

for i in range(newValue):
    newList.append('[')

for j in range(newValue2):
    newList2.append(']')

finalist = newList + newList2

for everChar in finalist:
    print everChar,

I now want the program to tell the user whether the brackets displayed are balanced or unbalanced. By this I mean whether it consists of entirely nested pairs.

So '[][][]' is balanced and '[]]][[]' is unbalanced.

When my module is running I want it to display some text saying 'balanced' or 'unbalanced' in regards to the brackets.

I have added this to my code, I am not sure why it is not working but I think I am along the right lines:

def balanced(input):
  opened = 0
  for c in input:
    if c == '[':
      openend += 1
    elif c == ']':
      opened -= 1

    if opened < 0:
        print 'Not Balanced'

    if opened > 0:
        print 'Not Balanced'

    if opened == 0:
        print 'Balanced'

        print opened
  return opened == 0

heavy version - use something like pyparsing with a custom grammar - after this, this is what compilers/intepreters do. if this is part of a larger effort, maybe look into that. for this small case, you just need to loop through the string, and keep a running count of which level you are at - `[` + 1, `]` - 1, if you ever go below 0, or end up above 0, it's not balanced. — Corley Brigman, Feb 28 '14 at 14:18
http://interactivepython.org/courselib/static/pythonds/BasicDS/stacks.html#simple-balanced-parentheses — M4rtini, Feb 28 '14 at 14:18
Ok, your code will always generate somthing like [[[]]]]] according to the random numbers generated so the only way to know it is balanced is newValue = newValue2 — Mohamed Abd El Raouf, Feb 28 '14 at 14:18
A string is a valid bracket sequence iif it contains as many opening as closing brackets and every prefix contains at least as many opening as closing brackets. Very simple to implement — Niklas B., Feb 28 '14 at 14:21
that code will never give `[][][]`. More general, it will never give a `]` before a `[` — M4rtini, Feb 28 '14 at 14:24
Why have you not used the answers to [your previous question](http://stackoverflow.com/questions/22019640/python-generating-random-string-of-brackets)? This code will give a random number of `'['` followed by a random number of `']'`. It certainly wouldn't give e.g. `'[][]][]][[][]'`. — jonrsharpe, Feb 28 '14 at 14:34

score 4 · Answer 1 · edited Feb 28 '14 at 14:50

4

For a general input consisting of [ and ] in any order:

def balanced(input):
  opened = 0
  for c in input:
    if c == '[':
      opened += 1
    elif c == ']':
      opened -= 1
    if opened < 0:
      return False
  return opened == 0

edited Feb 28 '14 at 14:50

Niklas B.

92,950
18
194
224

answered Feb 28 '14 at 14:35

blubb

9,510
3
40
82

This is what I was looking for thank you, however, when it is balanced how do I get it to display saying ''Balanced'' and also when it is unbalanced saying ''Unbalanced'' – Baileyavfc Feb 28 '14 at 14:41
@Baileyavfc: In this case, please accept the answer. The printing part is described here: http://www.learnpython.org/en/Conditions – blubb Feb 28 '14 at 14:47
i sure can... but it's better etiquette to give the original poster a chance to fix it first. after all, it's his code. at least, that's what i understood. – Corley Brigman Feb 28 '14 at 14:52

score 3 · Answer 2 · edited Feb 28 '14 at 14:32

3

For this code you just have to check if newValue == newValue2.

edited Feb 28 '14 at 14:32

jonrsharpe

115,751
26
228
437

answered Feb 28 '14 at 14:20

Saeid

4,147
7
27
43

This should have been a comment – thefourtheye Feb 28 '14 at 14:20
@thefourtheye i think he needs 50 rep to do that. And since OP's code does not do what he think it does. This is also the solution. – M4rtini Feb 28 '14 at 14:22
I know you can't make it comment but this answer i already wrote it in comments... – Mohamed Abd El Raouf Feb 28 '14 at 14:28

Determining a string's structure

2 Answers2