05.The Diwali Gift Boxes

EasyStack
Pattern lockedSolve it, or make 3 submissions, to unlock which classic problem this story hides.
A gift stall at a Diwali night market. A packing list shows the symbols ( [ ] ) { }. A closed round box holds a closed square box. An open curly box stands next to it.

// The story

Meena Aunty runs a Diwali gift shop in Jaipur. She packs gifts in boxes inside boxes.

She has three box shapes: round ( ), square [ ] and curly { }. Each order has a packing list of these symbols. An opening symbol opens a new box. It goes inside the newest open box, or on the counter if no box is open. A closing symbol is a lid for the newest box that is still open. The boxes inside must be closed first.

A round lid does not fit a square box. A lid with no open box is a mistake. So is a box left open at the end. Her helper Raju often misses these mistakes. Write a program to check each list.

// Your task

You are given a packing list s. Return true if the list is correct. Otherwise, return false.

Read the list from left to right:

  • (, [ and { open a new round, square or curly box. The new box goes inside the newest box that is still open. If no box is open, it goes on the counter.
  • ), ] and } are lids for round, square and curly boxes.
  • Each lid goes on the newest box that is still open. Then that box is closed.
  • The list is wrong if a lid comes when no box is open.
  • The list is wrong if the lid does not match the shape of the newest open box.
  • The list is wrong if any box is still open at the end.
  • If none of these happen, the list is correct.

Input: one line with the packing list s. It has no spaces.

Output: the program prints true or false on one line.

Limits: 1 ≤ length of s ≤ 104. The list has only the symbols ( ) [ ] { }.

Example 1:

Input:
([]){}

Output:
true

A round box opens. A square box opens inside it and gets its lid. Then the round box gets its lid. A curly box opens and closes. No box is left open.

Example 2:

Input:
([)]

Output:
false

A square box opens inside the round box. So the newest open box is square. The next lid ) is round, so it does not fit.

Example 3:

Input:
[()

Output:
false

The round box inside gets its lid. But the square box never gets a lid. It is still open at the end.

// Constraints

  • 1 ≤ length of s ≤ 10^4
  • s contains only ( ) [ ] { }

Time limit: 1s ·  Memory limit: 256 MB

Hint 1

Only the newest open box can take the next lid. So you must remember which boxes are open, and in what order.

Hint 2

Write the open boxes in a new row, in order. When a box opens, add it to the end of the row. A lid must match the last box in the row.

Hint 3

When a lid fits, remove the last box from the row. If the row is empty when a lid comes, the answer is false. At the end, the row must be empty.

Solution.cs
Sample tests