解压字符串

发布于 2019-04-01  8 次阅读


题目描述

给你一个字符串S,S是已经被加密过的字符串。现在要求你把字符串S还原。字符串S可能会出现这样的格式:k(q),它表示字符串q重复了k次,其中q是0个或多个字符,而k是一个数字,范围是0至9。你只要把k(q)这样的格式全部展开,就能把S还原了,你要输出还原后的字符串的长度。

输入

一行,一个字符串S。字符串S只由‘(’、‘)’、0至9的数字组成,长度不超过50。所有的括号都是能匹配的,不用判断。

输出

一个整数,还原后的字符串的长度。答案不会超过2147483647。

思路

找到最里面的一个括号,将里面没有被标记过的数加起来并且加上标记,加完后乘上前面的一个数,以此类推就可以了

var
  st:string;
  f:array[0..100] of boolean;
  i,j,k,n,m,x,y,l,r,le,s:longint;
  fl:boolean;
begin
  readln(st);
  le:=length(st);
  fl:=true;
  x:=0;
  while fl do
    begin
      fl:=false;
      for i:=le downto 1 do
        if (st[i]='(') and (not f[i]) then begin fl:=true; break; end;
      l:=i;
      for i:=l to le do
        if (st[i]=')') and (not f[i]) then begin fl:=true; break; end;
      r:=i;
      if not fl then break;
      s:=0;
      for i:=l-1 to r do
        if not f[i] then
        begin
          if i=l-1 then begin val(st[i],y); f[i]:=true; continue; end;
          if (st[i]<>'(') and (st[i]<>')') then
            x:=x+1;
          f[i]:=true;
        end;
      x:=x*y;
    end;
  for i:=1 to le do
    if not f[i] then inc(x);
  writeln(x);
end.

]]>