回 帖 发 新 帖 刷新版面

主题:[讨论]请各位帮我看道题目!!

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个回复)

沙发

奇怪的程序,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.

板凳

有错误的话请指正
还有你学了跟踪了没?没有的话快问老师,跟踪是找错利器。

3 楼

怎么发来发去就你们两人???
     作为副斑也不容易啊~~~~~~~~[em16]

4 楼

那你也发啊。。。。。。

5 楼

这个题目很简单呀!
不过这位同学把冬令营的试题发到网上寻求答案是不对滴!
建立一个栈
遇到'('或者'['的话就塞进去
一旦发现')'或者']'的话就和top进行比较
如果是')'top应该是'('
如果是']'top应该是'['
满足条件 退栈 top:=top-1
否则直接输出不符合条件
close一下然后exit

6 楼

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 楼

[quote]那你也发啊。。。。。。[/quote]

TO 贺天行宝:
    真不好意思,偶不会pascal,只是偶尔路过这里,顺道来看看撒。

                                   [em8][em8][em8]

8 楼

回1楼:能讲讲算法吗?   尤其是第二种

回5楼:你说的算法是老师讲的,我不也是用的这种方法吗?可程序还是有问题啊!!

9 楼

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 楼

程序可能有点问题
比如说语法等方面
不过我这题是满分

我来回复

您尚未登录,请登录后再回复。点此登录或注册