Member Avatar for magicMan123

I need to do the following question:

Turn a line of input containing matching pairs of round (()) or curly ({}) brackets into a mountain range. The height of the mountain should indicate how deeply nested the brackets are.

For example, given this input:

{({(){}()}{(){}()})({(){}()}{(){}()})({(){}()}{(){}()})}

Your program should output:

   (){}()  (){}()    (){}()  (){}()    (){}()  (){}()
  {      }{      }  {      }{      }  {      }{      }
 (                )(                )(                )
{                                                      }

If the brackets are not balanced (that is, a matching bracket appears when some of the brackets in the middle have not been closed), the program should print 'Invalid input!'.

please help!

  • 2 Contributors
  • 1 Reply
  • 327 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by slate

Dani AI

Generated

A simple, robust approach is: 1) validate the string with a stack while recording, for every bracket, its original column index and the nesting depth at which it appears; 2) compute the maximum depth; 3) build a canvas with one row per depth (top row = deepest) and one column per input character, place each bracket at its column in the row corresponding to its depth, then rstrip each printed line. 's parser already does the validation / depth collection — the missing step is turning those (char, index, depth) records into rows and printing them in the right order.

The key implementation details to watch for:

  • For an open bracket use the current stack size as its depth; for a close bracket pop the stack and use the popped open's depth for the close. That keeps open/close pairs aligned on the same row.
  • Use the original string index as the column so nested pairs naturally produce “mountain” gaps.
  • rstrip each output line to remove trailing spaces. If you want a narrower picture, post-process to collapse columns that are blank in every row (replace long blank runs between visible clusters with a single space).

Example Python routine (compact and different from the snippet above) that does validation + rendering:

def render_mountains(s):
    pairs = {')':'(', '}':'{'}
    stack = []
    records = []               # (char, index, depth)
    for i,ch in enumerate(s):
        if ch in '({':
            d = len(stack)
            stack.append((ch,i,d))
            records.append((ch,i,d))
        elif ch in ')}':
            if not stack or stack[-1][0] != pairs[ch]:
                print("Invalid input!")
                return
            o,oi,od = stack.pop()
            records.append((ch,i,od))
    if stack:
        print("Invalid input!")
        return

    maxd = max((d for _,_,d in records), default=0)
    rows = maxd + 1
    cols = len(s)
    grid = [[' '] * cols for _ in range(rows)]
    for ch,i,d in records:
        grid[maxd - d][i] = ch
    for row in grid:
        print(''.join(row).rstrip())

If you already have 's levels list, feed those pairs into the same grid-filling step above and you’ll get the mountain output.

Member Avatar for slate

Pretty printing is left as an exercise.
Edit: Error message on incomplete input.

inp="{({(){}()}{(){}()})({(){}()}{(){}()})({(){}()}{(){}()})}"
levels=list() # list of item, level pairs
stack=list()
cl=0 #current level
other={")":"(","}":"{"}
for it in inp:
  if it in ("(","{"):
    stack.append((it,cl))
    levels.append((it,cl))
    cl+=1
  else:
    if len(stack)==0 or other.get(it,'Impossible input')!=stack[-1][0]:
      print "Invalid input!"
      break
    else:
      m=stack.pop()
      levels.append((it,m[1]))
      cl=m[1]
else:
  if len(stack)!=0:
    print "Invalid input!"
  else:
    print levels
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.