PTIT123J PTIT spoj – Dấu ngoặc đúng
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT123J/ 1. Đề bài PTIT123J PTIT spoj Cho các đoạn văn chứa các dấu ngoặc, có thể là ngoặc đơn đơn ( “()” ) hoặc ngoặc vuông ( “[]” ). Một đoạn văn đúng là đoạn mà với mỗi dấu mở ngoặc thì sẽ có dấu đóng ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT123J/
1. Đề bài PTIT123J PTIT spoj
Cho các đoạn văn chứa các dấu ngoặc, có thể là ngoặc đơn đơn ( “()” ) hoặc ngoặc vuông ( “[]” ). Một đoạn văn đúng là đoạn mà với mỗi dấu mở ngoặc thì sẽ có dấu đóng ngoặc tương ứng và đúng thứ tự. Nhiệm vụ của bạn kiểm tra xem đoạn văn có đúng hay không.
Input
Gồm nhiều bộ test, mỗi bộ test trên một dòng chứa đoạn văn cần kiểm tra có thể bao gồm: các kí tự trong bảng chữ cái tiếng Anh, dấu cách, và dấu ngoặc (ngoặc đơn hoặc ngoặc vuông). Kết thúc mỗi bộ test là một dấu chấm. Mỗi dòng có không quá 100 kí tự.
Dữ liệu kết thúc bởi dòng chứa duy nhất một dấu chấm.
Output
Với mỗi bộ test, xuất ra trên một dòng “yes” nếu đoạn văn đúng, ngược lại in ra “no”.
Example
Input:
So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
.
.
Output:
yes
yes
no
no
no
yes
yes
############################################
Bài này sử dụng stack cơ bản. các bạn có thể tham khảo code….
2. code tham khảo PTIT123J PTIT spoj
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | const fi='; type data=longint; var f:text; S:ansistring; H:array[0..100000] of char; sta:data; procedure xuli; var i,j:data; begin sta:=0; for i:=1 to length(s) do begin if s[i] in ['(','['] then begin inc(sta); H[sta]:=s[i]; continue; end; if s[i] in [')',']'] then begin if ((s[i]=']') and (h[sta]='(')) or ((s[i]=')') and (h[sta]='[')) or (sta<=0) then begin writeln('no'); exit; end; dec(sta); end; end; if sta>0 then begin writeln('no'); exit; end; writeln('yes'); end; begin assign(f,fi); reset(f); while TRUE do begin readln(f,s); if s='.' then break; xuli; end; close(f); end. |
