Balanced parentheses with a stack

Mobile coding works. A laptop is faster for long sessions.

Problem

Read from standard input a string of at most 2000 characters that may contain round brackets ( ), square brackets [ ], curly braces { }, and any other characters (letters, digits, operators).

We say the string has balanced brackets if:

every opening bracket has a matching closing bracket of the same type;

brackets close in the reverse order of opening (they do not intersect).

Print DA if the brackets are balanced and NU otherwise.

Use a stack implemented with a character array and an index top. Do not use STL containers.

Input format

Input input.txt

The program reads from standard input a single string on one line. - the string has at most `2000` characters; - characters that are not brackets are ignored during the check; - a string with no brackets at all is considered balanced.

Output format

Output output.txt

The program prints to standard output the word `DA` or `NU`, followed by a newline.

Example

input

(a+[b-{c*d}])

output

DA

Sample cases (from the problem)

Sample Case 1

Input

(a+[b-{c*d}])

Expected output

DA

Ready to solve this challenge?

Create a free account to write code, submit solutions, and track your progress.

🔍 Interactive Debugger

0 / 0

Analyzing your code...

Problem

Input format

Output format

Example

Stuck?

💬 Discussion

Sample cases (from the problem)

Solve it your way first

Ready to solve this challenge?

🔍 Interactive Debugger

Error

Problem

Input format

Output format

Example

Stuck?

💬 Discussion

Sample cases (from the problem)

Solve it your way first

Ready to solve this challenge?

⌨️ Keyboard Shortcuts

🔍 Interactive Debugger

Error