xonix Jan 30 2009 at 20:37

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

1 min

6.2K

Comments 57

Vas3K Jan 30 2009 at 20:42

Это решают на уроках информатики в нормальных лицеях в 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 Jan 30 2009 at 20:47

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

Vas3K Jan 30 2009 at 20:47

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

EiZeRR Jan 30 2009 at 20:59

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

xonix Jan 30 2009 at 21:01

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

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

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

=)

EiZeRR Jan 30 2009 at 21:08

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

xonix Jan 30 2009 at 21:14

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

EiZeRR Jan 30 2009 at 21:16

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

Sannis Jan 31 2009 at 00:11

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

khayrov Jan 31 2009 at 00:13

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

Sannis Feb 1 2009 at 02:29

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

xonix Jan 31 2009 at 00:27

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

Sannis Feb 1 2009 at 02:32

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

Sannis Feb 1 2009 at 02:34

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

xonix Jan 30 2009 at 21:11

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

xexsus Jan 30 2009 at 22:11

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

bool(true) bool(false)

xonix Jan 30 2009 at 22:27

Oo не понятно…

xexsus Jan 30 2009 at 22:30

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

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

xexsus Jan 30 2009 at 22:38

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

Sannis Jan 31 2009 at 00:14

<? $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 Jan 31 2009 at 12:12

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

return count($stack)==0;

worklez Jan 30 2009 at 22:19

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 Jan 30 2009 at 22:23

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

1602 Jan 30 2009 at 22:45

Мой любимый язык — 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 Jan 30 2009 at 22:56

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

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 Jan 30 2009 at 23:05

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

keymone Jan 30 2009 at 23:44

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

tenshi Jan 30 2009 at 23:56

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

tenshi Jan 30 2009 at 22:47

UFO landed and left these words here

khayrov Jan 31 2009 at 00:09

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 Jan 31 2009 at 00:41

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

Вот эту строчку можно переписать чуть короче (давно не брал в руки CamlP4):
| [< c1 = paren; inner = parens; 'c2 >] -> inner && c1 = c2

Covex Jan 31 2009 at 00:11

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 Jan 31 2009 at 00:32

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

Covex Jan 31 2009 at 00:35

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

Covex Jan 31 2009 at 00:41

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

Covex Jan 31 2009 at 02:24

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

var check = (function(close) { var bracket = { }, ch, end; for (i in close) bracket[close[i]] = (function(i) { return function(pos) { if (ch[pos+1] == i) return pos+2; else if (bracket[ch[end = pos+1]]) while (end = bracket[ch[end]](end)) if (ch[end] == i) return end + 1; throw { }; } })(i); return function(str) { try { var pos = 0; while (pos < str.length) pos = bracket[(ch = str)[pos]](pos); return true; } catch (e) { return false; } }; })({ ')':'(', '>':'<', '}':'{', ']':'[' }); alert(check("[<>{}]")); // true alert(check("")); // true alert(check("[[[]]][][[]][()]{}[]")); // true alert(check("[[[)]]][][[]][()]{}[]")); // false alert(check("]")); // false * This source code was highlighted with Source Code Highlighter.

VoidEx Jan 31 2009 at 00:14

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

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 Jan 31 2009 at 00:52

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

-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 Jan 31 2009 at 00:55

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

xonix Jan 31 2009 at 01:11

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

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 Jan 31 2009 at 01:12

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

keymone Jan 31 2009 at 01:12

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

xonix Jan 31 2009 at 01:19

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

keymone Jan 31 2009 at 01:21

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

xonix Jan 31 2009 at 01:26

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

khim Jan 31 2009 at 02:09

Язык со встроенным парсером тут вряд ли удастся победить — всё-таки под подобные задачки 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 Jan 31 2009 at 02:20

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 Jan 31 2009 at 03:13

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

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 Feb 1 2009 at 03:00

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

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

xonix Feb 1 2009 at 03:24

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

mas Feb 1 2009 at 08:31

Конечно. Но очень часто этого будет вполне достаточно. Практически даже всегда. Строка из десяти миллионов символов проверяется за 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 Jan 31 2009 at 09:53

на 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 Jan 31 2009 at 10:04

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 Jan 31 2009 at 10:13

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

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 Jan 31 2009 at 16:01

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

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

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

stab May 27 2009 at 19:39

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);
}

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