Правильность скобочной структуры, prolog

[Vas3K]

Это решают на уроках информатики в нормальных лицеях в 11 классе. Задачка на использование стека.

Решение даже есть на вики: ru.wikibooks.org/wiki/Язык_Си_в_примерах/Скобочки

 #include <stdio.h>
 int main (void)
 {
     int ch, a=0;
     printf ("Введите слово из скобок: ");
     do {
         ch = getchar();
         if( ch == '(' ) a++;
         else if( ch == ')' ) if(--a < 0) break;
     } while(ch != '\n');
     if( a == 0) printf ("Правильно\n");
     else printf ("Не правильно\n");
     return 0;
 }

[xonix]

я ж не против ) только с несколькими видами скобок будет немного сложнее )

[Vas3K]

Ну я так понял у автора еще и скобочки могут быть разные. Тогда решение увеличивается на несколько строк, но смысл такой же.

[EiZeRR]

ну не совсем на несколько строк — для каждого вида скобок придется свою переменную вводить — это действительно просто, но вот обрабатывать такие ситуации как (([)]), по-моему это совсем не тривиально

[xonix]

там надо алгоритм поменять а именно — заталкивать открывающие скобочки в стек, а при закрывающих — доставать. если достать не получится (сверху не тот вид скобочки или нет скобочек) -> неверно.

если в конце что-то осталось -> не верно

иначе -> верно

=)

[EiZeRR]

ну алгоритм поменять — это не несколько строк добавить:) у меня в школе она вроде так и решалась, как вы описали:)
Все же на прологе более простое по размеру кода решение. На YACC, кстати, примерно так же и вышло бы.

[xonix]

угу, собственно тут применена надстройка над прологом в виде (DCG, есть в любом нормальном прологе) — это встраиваимые грамматики, которые автоматически транслируются в пролог-код.

[EiZeRR]

То-то мне показалось, что тут синтаксис какой-то странный:) Спасибо, не знал про такую штуку

[Sannis]

Т.е. по сути вы используете библиотеку. С тем же успехом можно было бы использовать в любом языке библиотеку парсера арифметических выражений, их как грязи :)

[khayrov]

Если я правильно понял, что такое DCG, то сравнивать надо не с парсером арифметических выражений, а с DSL для создания парсеров, вроде Spirit.

[Sannis]

Можно конечно, вопрос в том, что короче пишется, автор топика всё-таки имел в виду конкретную задачу :)

[xonix]

Не сказал бы. Ну, в принципе, это расширение языка, но оно встроено во все мало-мальски приличные реализации пролога, потому-что очень хорошо ложится на парадигму поиска с возвратом.

[Sannis]

Хм, тогда можно во многих языках использовать eval() для таких целей :)

[Sannis]

Не, глупость, для разных типов скобок не получится сделать.

[xonix]

собственно интересно как хорошо задача ложится на прологовский DCG

[xexsus]

php
Решение в лоб, хотя наверно можно решить красивее.

bool(true) bool(false)

[xonix]

Oo не понятно…

[xexsus]

НЛО съело мой код

вот тут положил:
taskrise.com/bracket.txt

[xexsus]

у кого теги держит, киньте код сюды, по ссылкам гулять не айс

[Sannis]

<?

$bracket=array(
 array('[',']'),
 array('(',')'),
 array('{','}')
);

function check($BracesStr)
{
 global $bracket;
 $stack=array();
 for($i=0;$i<strlen($BracesStr);$i++)
 {
  $ch=$BracesStr[$i];
  for($j=0;$j<count($bracket);$j++)
  {
   if($ch==reset($bracket[$j]))
   { // новая скобка, в стек её
    array_push($stack,$ch);
    break;
   }
   elseif($ch==end($bracket[$j]))
   { // закрытие скобки, проверка
    if(reset($bracket[$j])==end($stack))
    { // скобки совпадают
     array_pop($stack);
     break;
    }
    else
    { // нарушение структуры
     return false;
    }
   }
  }
 }
 return true;
}

echo var_dump(check("[[[]]][][[]][()]{}[]")); // bool(true)
echo var_dump(check("[[[)]]][][[]][()]{}[]")); // bool(false)

?>

* This source code was highlighted with Source Code Highlighter.

[xexsus]

опа, ошибка
последняя строчка функции должна быть такая:

return count($stack)==0;

[worklez]

module Main where
import System
import Text.ParserCombinators.Parsec

close "[" = "]"
close "(" = ")"
close "{" = "}"

squareBracket = string "["
roundBracket = string "("
brace = string "{"

openParens = squareBracket <|> roundBracket <|> brace
closeParens p = string (close p)

emptySequence = return $ ()

nonEmptySequence = do
	p <- openParens
	parentheses
	closeParens p
	parentheses	

parentheses = nonEmptySequence <|> emptySequence

main = do
	args <- getArgs
	putStrLn (check (args !! 0)) where
	check input = case parse parentheses "stdin" input of
			Left err -> "False: " ++ show err
			Right val -> "True"

% ./t "[[[]]][][[]][()]{}[]"
True
% ./t "[[[]]][][[]][()]{}["
False: «stdin» (line 1, column 20):
unexpected end of input
expecting "[", "(", "{" or "]"

На красоту решения не претендую, я только учусь. :)

[xonix]

спасибо, интересно. кстати, алгоритм почти 1 в 1 )

[1602]

Мой любимый язык — javascript.
Вот решение в лоб:

test = (function(){
    var pop = {')':'(','>':'<','}':'{',']':'[',')':'('};
    var stack = [];
    return function(string){
        for(var i=0;i<string.length;i++){
            var char = string.charAt(i);
            if(!pop[char]){
                stack.push(char);
            }else{
                if(stack.length==0 || stack.pop()!=pop[char])return false;
            }
        }
        return stack.length==0?true:false;
    }
})();
test('(())<>{}[]');

[1602]

или вот так будет покороче и попонятнее:

function test(s){
    var x = s.length+1;
    while(s = s.replace(/\<\>|\[\]|\{\}|\(\)/,'')){
        if(s.length==x && x!=0)return false;
        if(x==0)return true;
        x=s.length;
    }
    return true;
}

test('({<[]>})(((([))))');

[xonix]

алгоритм простой, но неоптимальный, при большой строке будет чересчур много копирования в памяти

[keymone]

это вообще то не жаваскрипт а рэгэксп…

[tenshi]

а что такое яваскрипт?

[tenshi]

var brackets=
{ '[': ']'
, '{': '}'
, '(': ')'
};

function check( BracesStr ){
return phrase( brackets, BracesStr );
}

check( "[[[]]][][[]][()]{}[]" ); // true
check( "[[[)]]][][[]][()]{}[]" ); // false

[khayrov]

OCaml + CamlP4

let paren = parser
    | [< ''(' >] -> ')'
    | [< ''[' >] -> ']'

let rec parens = parser
    | [< c1 = paren; inner = parens; c2 = Stream.next >] -> inner && c1 = c2
    | [< >] -> true;;

let parse = parser [< valid = parens; _ = Stream.empty >] -> valid

let check s =
    try parse (Stream.of_string s)
    with Stream.Error _ | Match_failure _ -> false

[khayrov]

| [< c1 = paren; inner = parens; c2 = Stream.next >] -> inner && c1 = c2

Вот эту строчку можно переписать чуть короче (давно не брал в руки CamlP4):

| [< c1 = paren; inner = parens; 'c2 >] -> inner && c1 = c2

[Covex]

JavaScript:

var check = (function(close) {
 var open = { };
 for (i in close)
  open[close[i]] = i;

 return function(str) {
  var first=0, begin = 0, end = 1, len = str.length;
  while (first < len) {
   if (close[str[end]] == str[begin]) {
    if (begin == first)
     begin = first = ++end;
    else
     begin--;
   }
   else if (open[str[end]])
    begin++;
   else
    return false;
   end++;
  }
  return true;
 };
})({ ')':'(', '>':'<', '}':'{', ']':'[' });

alert(check("[[[]]][][[]][()]{}[]")); // true
alert(check("[[[)]]][][[]][()]{}[]")); // false

* This source code was highlighted with Source Code Highlighter.

Без стэка =)

[xonix]

зато алгоритм какой-то непонятный…

[Covex]

Понятный алгоритм со стэком уже 1602 выложил =)

[Covex]

А ещё мой вариант быстрее в 4 раза.

[Covex]

А ещё этот код — не рабочий =( С [{}{}] он работает неверно. Вот новый, рекурсивный:

1. var check = (function(close) {
2.  var bracket = { }, ch, end;
3.  for (i in close)
4.   bracket[close[i]] = (function(i) {
5.    return function(pos) {
6.     if (ch[pos+1] == i)
7.      return pos+2;
8.     else if (bracket[ch[end = pos+1]])
9.      while (end = bracket[ch[end]](end))
10.       if (ch[end] == i)
11.        return end + 1;
12.     throw { };
13.    }
14.   })(i);
15.  
16.  return function(str) {
17.   try {
18.    var pos = 0;
19.    while (pos < str.length)
20.     pos = bracket[(ch = str)[pos]](pos);
21.    return true;
22.   }
23.   catch (e) {
24.    return false;
25.   }
26.  };
27. })({ ')':'(', '>':'<', '}':'{', ']':'[' });
28.  
29. alert(check("[<>{}]")); // true
30. alert(check("")); // true
31. alert(check("[[[]]][][[]][()]{}[]")); // true
32. alert(check("[[[)]]][][[]][()]{}[]")); // false
33. alert(check("]")); // false

* This source code was highlighted with Source Code Highlighter.

[VoidEx]

С прологом в таком примере, конечно, тягаться почти нереально :)
Так что я даже не пытаюсь, просто ещё одно решение.

import Data.List

bracket '[' = Just ']'
bracket '(' = Just ')'
bracket '{' = Just '}'
bracket _ = Nothing

brackets [] = True
brackets [x] = False
brackets (l:r:s)
    | Just r' <- bracket l
    , True <- r' == r
    = brackets s
    | Just r' <- bracket l
    , sub <- last $ filter brackets $ inits (r:s)
    , (r'':tl) <- drop (length sub) (r:s)
    , True <- r'' == r'
    = brackets tl
    | otherwise = False


[keymone]

а вот и эрланговский вариант:

-module(brackets).
-export([check/1]).

close($() -> $);
close($[) -> $];
close(${) -> $};
close(_) -> not_opening.

check(List) ->
    check(List, []).

check([], []) -> ok;
check([], _) -> error;
check([H1|T1], []) -> check(T1, [H1]);
check([H1|T1], [H2|T2]=L) ->
    case close(H2) of
        H1 -> check(T1, T2);
         _ -> check(T1, [H1|L])
    end.

> brackets:check("[[[]]][][[]][()]{}[]").
ok
> brackets:check("[[[)]]][][[]][()]{}[]").
error

пользует хвостовую рекурсию, чем пролог вроде как похвастаться не может ;)

[keymone]

а ну и это обычный стэковый вариант решения задачи

[xonix]

кстати, за неимением под рукой эрланга и интереса ради переписал почти дословно ваше решение на прологе:

close_("(", ")").
close_("[", "]").
close_("{", "}").

check(List) :-
    check(List, []), !.

check([H1|T1], []) :-
    check(T1, [H1]).
check([H1|T1], [H2|T2]) :-
    ( close_([H2], [H1])
        -> check(T1, T2)
    ; check(T1, [H1, H2|T2])
    ).

check([], []).



?- check("[[[]]][][[]][()]{}[]").
true.

?- check("[[[)]]][][[]][()]{}[]").
false.


[xonix]

сказывается то, что пролог был прародителем эрланга )

[keymone]

шикарно! и вобщем ожидаемо, так как эрланг — прямой потомок пролога.

[xonix]

и по поводу хвостовой рекурсии — пролог ее поддерживает, кстати

[keymone]

я имел ввиду первый, предложенный вами вариант.

[xonix]

если в конце первой части предиката brackets поставить отсечение (!) то, что-то мне подсказывает, все оптимизируется как надо )

[khim]

Язык со встроенным парсером тут вряд ли удастся победить — всё-таки под подобные задачки DCG сильно заточен. Попробуйте на прологе без DCG то же сделать — тут уже будет куда ближе к обычным языкам. Вот на scheme:

(define (bracket x)
  (cond
    ((char=? #\( x) #\))
    ((char=? #\[ x) #\])
    ((char=? #\{ x) #\})
    (else #f)))

(define (brackets v e l)
  (if (eq? l '())
    v
    (if (eq? (car l) e)
      (cdr l)
      (let ((b (bracket (car l))) (r (cdr l)))
        (if b
          (let ((u (brackets #f b r)))
            (if (eq? u #f)
              #f
              (brackets v e u)))
          #f)))))

(define (check s)
  (brackets #t #f (string->list s)))

[mas]

Python:

BRACES = { '[':']', '{':'}', '(':')' }

def check( s, x='' ):
  if len(s)==‍0: return len(x)==‍0
  if s[­0] in BRACES: return check( s[1:], BRACES[s[­0]]+x )
  if len(x)==­0: return False
  if s[­0]==x[­0]: return check( s[1:], x[1:] )
  return False

assert check( "[[[]]][][[]][()]{}[]" )  == True
assert check( "[[[)]]][][[]][()]{}[]" ) == False


[TimTowdy]

Неоптимально, но коротко (теги мне нельзя, поэтому "_" вместо пробела):

def check(seq, old=''):
____while old != seq:
________old = seq
________for b in ['[]', '{}', '()']:
____________seq = seq.replace(b, '')
____return seq == ''

print check("[[[]]][][[]][()]{}[]") # True
print check("[[[)]]][][[]][()]{}[]") # False

[mas]

Хороший подход!

Иногда в текстовом редакторе заменами можно делать довольно нетривиальные вещи.

[xonix]

по оптимальности алгоритма таки плохой… при большой строке из скобок будет чересчур много копирования в памяти

[mas]

Конечно. Но очень часто этого будет вполне достаточно. Практически даже всегда. Строка из десяти миллионов символов проверяется за 0.47 с. Кстати, гораздо дольше её генерировать, если использовать обратный алгоритм — в случайное место вставлять случайную пару скобок. 100 тыс пар за 12 с.

def check(t):
ol = 0
nl = len(t)
while ol!=nl:
ol = nl
t = t.replace("()","").replace("[]","").replace("{}","")
nl = len(t)
return nl==0


[youlose]

на perl:

#!/usr/bin/perl -w
use 5.010;
use strict;
my %bracers = (']'=>'[',')'=>'(','}'=>'{');
sub TRUE { 'true' };
sub FALSE { 'false' };
sub check {
    my @buf;
    for (split '',shift || $_) {
        if (defined $bracers{$_}) {
            return FALSE if pop @buf ne $bracers{$_};
        } else {
            push @buf,$_;
        }
    };
    return $_ ? TRUE : FALSE;
}
foreach ( "[[[]]][][[]][()]{}[]" , "[[[)]]][][[]][()]{}[]" , "{}{}", '') {
    say "$_ - ",check();
}


Результат:

[[[]]][][[]][()]{}[] — true
[[[)]]][][[]][()]{}[] — false
{}{} — true
— false

[iv_s]

Ruby, влоб со стеком:

def invert c
  return ')' if c == '('
  (c[0] + 2).chr
end

def check str
  stack = []
  str.split(//).each do |c|
    if c =~ /[\{\[\(]/
      stack.push c
    elsif c =~ /[\}\]\)]/
      return false if c != invert(stack.pop)
    else
      return false
    end
  end
  true
end

puts check('[[[]]][][[]][()]{}[]') #=> true
puts check('[[[)]]][][[]][()]{}[]') #=> false

[iv_s]

Тоже, только короче:

def check str
  stack = []
  str.split(//).each do |c|
    if '{[('.include? c
      stack.push c
    else
      return false if c != stack.pop.tr('{[(','}])')
    end
  end
  true
end

puts check('[[[]]][][[]][()]{}[]') #=> true
puts check('[[[)]]][][[]][()]{}[]') #=> false

[iv_s]

Решил еще немного поиграться:)
Решение в две строчки:

def check str
  str.gsub!(/(\[\]|\(\)|\{\})/, '') while str =~ /(\[\]|\(\)|\{\})/
  str == ''
end

puts check('[[[]]][][[]][()]{}[]') #=> true
puts check('[[[)]]][][[]][()]{}[]') #=> false

[stab]

C(++)

bool validate(char *text, void *stack)
{
   unsigned char *stack_ptr = (unsigned char *) stack;
   while (unsigned char ch = (unsigned char) *text++)
      if (!(ch & 1 ^ (ch & 2) >> 1)) *stack_ptr++ = ch;
      else if (stack == stack_ptr || *--stack_ptr - ch > 2) return false;
   return stack == stack_ptr; 
}

void main()
{
   void *stack = malloc(4 * 1024);
   printf(validate("[[[]]][][[]][()]{}[]", stack) ? "valid\n" : "invalid\n");
   printf(validate("[[[)]]][][[]][()]{}[]", stack) ? "valid\n" : "invalid\n");
   free(stack);
}

В реальных проектах я конечно так не пишу :)