栈的模拟运用 SOJ3897 dance2

绝地灬酷狼 2022-03-29 04:48 63阅读 0赞

dance2

Time Limit: 3000 MS    Memory Limit: 65536 K

--------------------

## Description ##

The cow cotillion, a fancy dance every spring, requires the cows  
(shown as ">") and bulls (shown as "<") to bow to each other during  
a dance. Schematically, one properly bowing pair of cattle is shown  
like this: "><". Sometimes another pair of cattle will sashay between  
a pair of bowing cows: "> >< <".  
  
In fact, sometimes a larger number of cows will mix it up on the  
dance floor: "> >< < ><" (this includes a second set of bowing cows  
on the right). Complex arrangements can be perfectly legal dance  
formations:  
              > > > >< < >< < >< >< >< <  
  
              | | | -- | -- | -- -- -- |  
              | | ------    |          |  
              | -------------          |  
              --------------------------  
  
Farmer John notices that a stray heifer sometimes sneaks into a  
group and unbalances it: "> >< < <><". This is strictly forbidden;  
FJ wants to punish the interlopers.  
  
FJ has copied down records of as many as 500 cows participating in  
dance lines and wonders if the dance line is properly balanced  
(i.e., all of the cattle can be paired off in at least one way as  
properly bowing pair by pair). He copied only the direction each  
cow was bowing without any extra spaces to help determine which cow  
was bowing to which bull, strings like this rendition of the illegal  
example from the previous paragraph: ">><<<><". He wants you to  
write a program to tell him if the dance line is legal.  
  
FJ has N (1 <= N <= 1,000) pattern recordings P\_i comprising just  
the characters '>' and '<' with varying length K\_i (1 <= K\_i <=  
200).  Print "legal" for those patterns that include proper pairs  
of bowing cows and "illegal" for those that don't.

## Input ##

\* Line 1: A single integer: N  
  
\* Lines 2..N+1: Line i contains an integer followed by a space and a  
        string of K characters '>' and '<': K\_i and P\_i

## Output ##

\* Lines 1..N: Line i contains either the word "legal" or "illegal"  
        (without the quotes, of course) depending on whether the input  
        has a legal bowing configuration.

## Sample Input ##

2  
6 >><<><  
4 ><<>

Sample Output

legal  
illegal

题意：就是给出一行字符串，仅包括符号'>'和'<'，然后判断是否匹配，其实跟括号匹配的判断原理相同，就是来模拟栈。

其过程如下:

1)如果遇到'>',直接push;

2)如果遇到'<',如果栈非空且栈顶字符为'>'，则进行pop;

否则进行push;

3)最后，如果栈为空，则是合法的；否则不合法；

\#include < iostream >   
\#include < algorithm >   
\#include < stack >   
 using namespace  std;  
  
 int  main( void )  
\{  
 int  t,n;  
 char  ch;  
 while (scanf( " %d " , & t) == 1 )  
\{  
 for ( int  i = 0 ;i < t;i \++ )  
\{  
 int  flag = 0 ;  
stack < char >  st;  
scanf( " %d  " , & n);  
 for ( int  j = 0 ;j < n;j \++ )  
\{  
scanf( " %c " , & ch);  
 if (ch == ' < ' &&! st.empty() && st.top() == ' > ' )  
\{  
st.pop();  
 continue ;  
\}  
st.push(ch);  
\}  
 if (st.empty())  
printf( " legal\\n " );  
 else   
printf( " illegal\\n " );  
\}  
\}  
 return 0 ;  
\}