| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 9091 | Web Navigation |
|
| 9100 | Parentheses Matching |
|
Description
It is a common feature that the web browsers support moving backward and forward among the pages recently visited. Please simulate this function, which uses two stacks, backward stack and forward stack, and is commanded by following keywords.
(1) VISIT <url> - Push the current page on the top of the backward stack, and make the page specified by URL become the new current page. The entries in forward stack are then discarded.
(2) BACK - Push the current page on the top of the forward stack and pop the page from the top of the backward stack, which becomes the new current page. If the backward stack is empty, this command should be ignored.
(3) FORWARD - Push the current page on the top of the backward stack and pop the page from the top of the forward stack, which becomes the new current page. If the forward stack is empty, this command should be ignored.
Assume that the browser initially loads the web page at the URL “http://www.acm.org/”.
Input
There is only one set of commands in the input. Each command occupies a line, and the length of URLs will be no more than 100 and they contain no space character. The number of commands will be no more than 100000, and the input is terminated by end-of-file (EOF). You may assume that the entries in the stack will be no more than 10000 at any time.
Output
For each command, output the URL of the current page after the command is executed, in a line. In case that the command is ignored, print “Ignored” instead.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A string is said to be valid if it matches one of the following rules:
(1) The string is an empty string.
(2) If a string S is valid, then {S}, [S], (S) and <S> are valid.
(3) If strings S1 and S2 are both valid, then S1S2 is valid.
Given a string consisting of parentheses, determine if it is a valid string.
Input
The first line of the input contains an integer N (N ≤ 1000) denoting the number of test cases followed by. Each of the next N lines corresponds to a test case, which contains a string consisting of parentheses, and the maximum string length will be no more than 1000. Note that an empty string (a line which contains the newline character only) may be contained in the input and it should be considered as a valid string according to rule (1).
Output
For each test case, print “Case i:” and then “Yes” or “No” to indicate that the string is valid or not, separated by a space character. i is the test case number starting from 1.