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

Это решают на уроках информатики в нормальных лицеях в 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;
 }

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

bool(true) bool(false)

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 "]"

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

Мой любимый язык — 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('(())<>{}[]');

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

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

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

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

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.

Без стэка =)

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

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


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

-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

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

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

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


на 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

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

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

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