主题:[讨论]请各位帮我看道题目!!
编程黑客
[专家分:1660] 发布于 2007-02-13 13:40:00
1. 括弧匹配检验work1.???(pas,c,cpp)
假设表达式中允许包含两种括号:圆括号和方括号,其嵌套的顺序随意,如([ ]())或[([ ][ ])]等为正确的匹配,[( ])或([ ]( )或 ( ( ) ) )均为错误的匹配。
现在的问题是,要求检验一个给定表达式中的括弧是否正确匹配?
输入一个只包含圆括号和方括号的字符串,判断字符串中的括号是否匹配,匹配就输出 “OK” ,不匹配就输出“Wrong”。
输入一个字符串:
[([][])]
输出:
OK
【输入】
输入仅一行字符(字符个数小于255)
【输出】
匹配就输出 “OK” ,不匹配就输出“Wrong”。
【样例】
输入(work1.in)
[(])
输出(work1.out)
Wrong
我用栈做的,程序是:
type arraytype=array[0..255] of char;
var s:arraytype;
i,j,top:integer;
ch,x:char;
procedure push(var stack:arraytype;n:char);
begin
top:=top+1;
stack[top]:=n;
end;
procedure pop(var stack:arraytype);
begin
x:=stack[top];
top:=top-1;
end;
function empty(var stack:arraytype):boolean;
begin
if top=0 then empty:=true else empty:=false;
end;
function pei(a,b:char):boolean;
begin
if a='(' then
if b=')' then pei:=true else pei:=false
else
if b=']' then pei:=true else pei:=false;
end;
begin
assign(input,'work1.in');
assign(output,'work1.out');
reset(input);rewrite(output);
j:=0;top:=0;
while not(eof()) do
begin
j:=j+1;
read(s[j]);
end;
for i:=1 to j do
begin
if (s[i]='(') or (s[i]='[') then
push(s,s[i])
else
begin
pop(s);
if pei(x,s[i])=false then begin
writeln('Wrong');
halt;
close(input);
close(output)
end;
end;
end;
if empty(s)=true then writeln('Ok') else writeln('Wrong');
close(input);close(output);
end.
有点错误,请各位帮帮忙!!
回复列表 (共12个回复)
沙发
贺天行宝 [专家分:2300] 发布于 2007-02-13 19:52:00
奇怪的程序,STACK不是全局变量?S怎么是数组?
而且这种题应该有更简单的做法。
堆:
var
s:string;
stack:array[0..255]of char;
c:char;
i,j,k,l,m,n,top:longint;
procedure push(c:char);
begin
inc(top);
stack[top]:=c;
end;
procedure pop(var c:char);
begin
c:=stack[top];
dec(top);
end;
function pei(a,b:char):boolean;
begin
pei:=false;
if a='(' then if b=')' then pei:=true else
else if b=']' then pei:=true;
end;
function empty:boolean;
begin
empty:=false;
if top=0 then empty:=true;
end;
begin
readln(s);stack[0]:=' ';top:=0;
for i:=1 to length(s) do
begin
if (s[i]='(')or(s[i]='[') then push(s[i])
else begin
pop(c);
if not pei(c,s[i]) then begin top:=1;{for the last empty}break; end;
end;
end;
if not empty then writeln('wrong') else writeln('OK');
end.
加减法
1:() 2:[]
var
s:string;
a:array[1..256]of longint;
num:array[1..2]of longint;
i,j,k,l,m,n:longint;
begin
readln(s);
{writeln(ord('('),' ',ord(')'),' ',ord('['),' ',ord(']'));
40 41 91 93 }
num[1]:=0;num[2]:=0;
a[40]:=1;a[41]:=1;a[91]:=2;a[93]:=2;{direction to num}
for i:=1 to length(s) do
begin
k:=ord(s[i]);
if (s[i]='(')or(s[i]='[') then inc(num[a[k]])
else dec(num[a[k]]);
if (num[1]<0)or(num[2]<0) then break;
end;
if (num[1]=0)and(num[2]=0) then writeln('OK') else writeln('wrong');
end.
板凳
贺天行宝 [专家分:2300] 发布于 2007-02-13 19:55:00
有错误的话请指正
还有你学了跟踪了没?没有的话快问老师,跟踪是找错利器。
3 楼
merry05 [专家分:8920] 发布于 2007-02-13 23:50:00
怎么发来发去就你们两人???
作为副斑也不容易啊~~~~~~~~[em16]
4 楼
贺天行宝 [专家分:2300] 发布于 2007-02-14 10:23:00
那你也发啊。。。。。。
5 楼
bigchen [专家分:1940] 发布于 2007-02-15 20:09:00
这个题目很简单呀!
不过这位同学把冬令营的试题发到网上寻求答案是不对滴!
建立一个栈
遇到'('或者'['的话就塞进去
一旦发现')'或者']'的话就和top进行比较
如果是')'top应该是'('
如果是']'top应该是'['
满足条件 退栈 top:=top-1
否则直接输出不符合条件
close一下然后exit
6 楼
bigchen [专家分:1940] 发布于 2007-02-15 20:15:00
PS:这个题目可以优化一下
……
if (a[i]='(') or (a[i]='[') then l1:=l1+1;
if (a[i]=')') or (a[i]=']') then l2:=l2+1;
if l1<>l2 then
begin
writeln('Wrong');
close(input);
close(output);
exit;
end
else
……
就是先统计左括号和右括号的数量
如果数量不相等,就可以直接判断不符合条件
节约了程序执行的时间
当然,不优化也是可以的
因为这个数组(栈)打死了也只有255个字符
电脑是不在乎的
7 楼
merry05 [专家分:8920] 发布于 2007-02-16 00:06:00
[quote]那你也发啊。。。。。。[/quote]
TO 贺天行宝:
真不好意思,偶不会pascal,只是偶尔路过这里,顺道来看看撒。
[em8][em8][em8]
8 楼
编程黑客 [专家分:1660] 发布于 2007-02-16 21:42:00
回1楼:能讲讲算法吗? 尤其是第二种
回5楼:你说的算法是老师讲的,我不也是用的这种方法吗?可程序还是有问题啊!!
9 楼
bigchen [专家分:1940] 发布于 2007-02-17 16:38:00
var
a:packed array[1..300] of char;s:string;
n,i,j,k,l,top,l1,l2:integer;
begin
assign(input,'work1.in');reset(input);
assign(output,'work1.out');rewrite(output);
readln(s);l:=length(s);
if (s[1]=')') or (s[1]=']') then
begin
writeln('Wrong');close(input);
close(output);exit;
end;
for i:=1 to l do
begin
if (s[i]='(') or (s[i]='[') then l1:=l1+1;
if (s[i]=')') or (s[i]=']') then l2:=l2+1;
end;
if l1<>l2 then
begin
writeln('Wrong');close(input);
close(output);exit;
end;
for i:=1 to l do
begin
if (s[i]='(') or (s[i]='[') then
begin
top:=top+1;
a[top]:=s[i];
end
else
if (s[i]=')') and (a[top]='(') then
top:=top-1
else
if (s[i]=']') and (a[top]='[') then
top:=top-1
else
begin
writeln('Wrong');close(input);
close(output);exit;
end;
end;
writeln('OK');
close(input);close(output);
end.
10 楼
bigchen [专家分:1940] 发布于 2007-02-17 16:40:00
程序可能有点问题
比如说语法等方面
不过我这题是满分
我来回复