Оценка скобок и скобок как целых

20

Напишите программу, которая принимает строку из четырех символов, ()[]которая удовлетворяет этим требованиям:

  • Каждая левая скобка (имеет соответствующую правую скобку ).
  • Каждая левая скобка [имеет соответствующую правую скобку ].
  • Соответствующие пары скобок и скобок не будут перекрываться. Например [(]), недопустимо, потому что соответствующие скобки не полностью содержатся в соответствующих скобках, и наоборот.
  • Первый и последний символы - это совпадающая пара скобок или скобок. Так ([]([]))и [[]([])]есть, но []([])это не так.

( Грамматика для формата ввода есть <input> ::= [<input>*] | (<input>*).)

Каждая пара соответствующих скобок и скобок оценивается как неотрицательное целое число:

  • Значения пар внутри соответствующих скобок суммируются . Пустое совпадение ()имеет значение 0.
  • Значения пар внутри соответствующих скобок умножаются . Пустое совпадение []имеет значение 1.

( Сумма или произведение одного числа является тем же самым числом.)

Например, ([](())([][])[()][([[][]][][])([][])])может быть разбит и оценен как 9:

([](())([][])[()][([[][]][][])([][])])    <input>
(1 (0 )(1 1 )[0 ][([1 1 ]1 1 )(1 1 )])    <handle empty matches>
(1 0   2     0   [(1     1 1 )2     ])    <next level of matches>
(1 0   2     0   [3           2     ])    <and the next>
(1 0   2     0   6                   )    <and the next>
9                                         <final value to output>

Другой пример:

[([][][][][])([][][])([][][])(((((([][]))))))]    <input>
[(1 1 1 1 1 )(1 1 1 )(1 1 1 )((((((1 1 ))))))]
[5           3       3       (((((2     )))))]
[5           3       3       ((((2       ))))]
[5           3       3       (((2         )))]
[5           3       3       ((2           ))]
[5           3       3       (2             )]
[5           3       3       2               ]
90                                                <output>

Ваша программа должна оценить и напечатать целое число, представленное всей входной строкой. Вы можете предположить, что ввод действителен. Самый короткий код в байтах побеждает.

Вместо программы вы можете написать функцию, которая принимает строку и печатает или возвращает целое число.

Кальвин Хобби
источник
Запрашиваемая от имени Python для уточнения: только программа, или функции / возвращаемое значение в порядке?
Sp3000
Тогда, возможно, будет хорошо отредактировать вопрос. В предыдущем вопросе мне сказали, что функции недействительны, если в вопросе написано «написать программу».
Рето Коради

Ответы:

11

CJam, 23

q"])(""1]:*0]:+["4/ers~

С БОЛЬШИМИ кредитами Денису! Попробуйте онлайн

Объяснение:

Программа преобразует входные данные в выражение CJam, а затем оценивает его.
[…]становится […1]:*(добавить 1 и умножить)
(…)становится […0]:+(добавить 0 и добавить)

q              read input
"])("          characters we want to replace
"1]:*0]:+["    replacement strings, concatenated
4/             split into strings of length 4: ["1]:*" "0]:+" "["]
er             replace (transliterate) the 3 characters with the 3 strings
s              convert the result (mixed characters and strings) to string
~              evaluate
aditsu
источник
1
Транслитерация сохраняет 4 байта:q"])(""1]:*0]:+["4/ers~
Деннис
2
@ Денис, аааа! Это безумие, вы можете сделать это ??
aditsu
3
Вы спрашиваете меня ? : P
Деннис
4
@Dennis Как бы создатель CJam узнал о существовании такой функции ??
Оптимизатор
8

Common Lisp - 98

(lambda(s)(eval(read-from-string(#1=ppcre:regex-replace-all"\\["(#1#"]"(#1#"\\("s"(+")")")"(*"))))
  1. Заменить (на(+
  2. Заменить [на(*
  3. Заменить ]на)
  4. Читать из строки
  5. Eval

Это требует cl-ppcreзагрузки библиотеки в текущее изображение lisp.

объяснение

Функции *и +являются переменными и возвращают свое нейтральное значение, когда не приводятся аргументы. Для ваших примеров, оцененная форма lisp:

(+ (*) (+ (+)) (+ (*) (*)) (* (+)) (* (+ (* (*) (*)) (*) (*)) (+ (*) (*))))
=> 9

и

(* (+ (*) (*) (*) (*) (*)) (+ (*) (*) (*)) (+ (*) (*) (*))
   (+ (+ (+ (+ (+ (+ (*) (*))))))))
=> 90

Без регулярных выражений - 183 байта

(lambda(s)(do(r(x(coerce s'list))c)((not x)(eval(read-from-string(coerce(reverse r)'string))))(setq c(pop x))(push(case c(#\[ (push #\* r)#\()(#\] #\))(#\( (push #\+ r) #\()(t c))r)))

Да ладно, Лисп - 16 байт (экспериментальный)

+((<r*([<r)]<rRE

Другие языки настолько лаконичны, что я испытываю желание создать свой собственный язык для игры в гольф на основе Common Lisp для более коротких манипуляций со струнами. В настоящее время нет спецификаций, и функция eval является следующей:

(defun cmon-lisp (expr &rest args)
  (apply
   (lambda (s)
     (let (p q)
       (loop for c across expr
             do (case c
                  (#\< (push (pop p) q))
                  (#\r
                   (let ((a1 (coerce q 'string)) (a2 (coerce p 'string)))
                     (setf p nil
                           q nil
                           s
                             (cl-ppcre:regex-replace-all
                              (cl-ppcre:quote-meta-chars a1) s a2))))
                  (#\R
                   (setf s
                           (if (string= s "")
                               nil
                               (read-from-string s))))
                  (#\E (setf s (eval s)))
                  (t (push c p))))
       s))
   args))

тесты:

(cmon-lisp "+((<r*([<r)]<rRE" "([] [] ([] []))")
=> 4
  • есть неявный аргумент, который называется sи два стека, pи q.
  • символы в исходном коде помещаются в p.
  • <: выскакивает pи толкает к q.
  • r: заменяет в s(должно быть строкой) символы в qсимволы в p; результат сохраняется в s; pи qопустошены.
  • R: чтение из строки s, сохранение результата в переменной s.
  • E: eval form s, сохранить результат в s.
CoreDump
источник
1
Funyy, как lisp используется для скобок.
Сид Керкхове
@SydKerckhove Вы комментируете, только заставляете меня думать о соответствующем ответе Clojure. Большое спасибо!
coredump
6

Pyth, 35 34 33 байта

L?*F+1yMbqb+YbsyMbyvsXzJ"])"+R\,J

Демонстрация.

1 байт благодаря @Jakube.

Начнем с разбора ввода. Формат ввода близок к Python, но не совсем. Нам нужны запятые после каждой группы в скобках или в скобках. Запятая в конце группы в скобках не нужна, но безвредна. Для этого мы используем этот код:

vsXzJ"])"+R\,J
  X               Translate
   z              in the input
     "])"         the characters "])"
    J             which we will save to J to
             J    J
         +R\,     with each character mapped to itself plus a ",".
 s                Combine the list to a string.
v                  Evaluate as a Python literal.

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

Теперь, когда строка проанализирована, мы должны найти ее значение. Это делается с помощью пользовательской функции y, которая вызывается для анализируемого объекта. функция определяется следующим образом:

L?*F+1yMbqb+YbsyMb
L                     Define a function, y(b), which returns the following:
 ?       qb+Yb        We form a ternary whose condition is whether the input, b,
                      equals the inputplus the empty list, Y. This is true if
                      and only if b is a list.
      yMb             If so, we start by mapping y over every element of b.
  *F+1                We then take the product of these values. The +1 ensures
                      that the empty list will return 1.
                yMb   Otherwise, we start by mapping y over every element of b.
               s      Then, we sum the results.
isaacg
источник
@Jakube Правильно, унарное суммирование не имеет никакого эффекта.
Исаак
3

Emacs lisp, 94

Формат выглядит очень странным, поэтому я подумал, что может сработать простое преобразование:

(defun e()(format-replace-strings'(("("."(+")("["."(*")("]".")")))(eval(read(buffer-string))))

Промежуточный формат выглядит примерно так (для примера в вопросе):

(+(*)(+(+))(+(*)(*))(*(+))(*(+(*(*)(*))(*)(*))(+(*)(*))))

Нам помогает тот факт, что сложение и умножение уже делают то, что мы хотим, с пустым списком аргументов.

Дегольфед, и интерактив, для вас удовольствие от игры:

(defun paren_eval()
  (interactive "*")
  (format-replace-strings '(("(" . "(+")
                            ("[" . "(*")
                            ("]" . ")")))
  (eval (read (buffer-string)))
)
Тоби Спейт
источник
Я должен был прочитать более внимательно - решение Common Lisp использует точно такой же подход!
Тоби Спейт
1
Нам нужно больше ответов Emacs Lisp !. Кстати, я не считал, но вы могли бы поиграть в это немного больше, используя лямбду, взяв строку в качестве параметра и удалив interactive (вместо строки буфера используйте read-from-string).
coredump
2

Сетчатка , 111 байт

[\([](1+x)[]\)]
$1
\[]
1x
\(\)
x
(\[a*)1(?=1*x1*x)
$1a
a(?=a*x(1*)x)
$1
(\[1*x)1*x
$1
)`(\(1*)x(?=1*x)
$1
[^1]
<empty line>

Дает вывод в одинарный.

Каждая строка должна идти в свой собственный файл, но вы можете запустить код как один файл с -sфлагом. Например:

> retina -s brackets <input_1
111111111

Объяснение приходит позже.

randomra
источник
2

Ява, 349 символов

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

import java.util.*;class K{int a=0,b;String c;public static void main(String[]a){K b=new K();b.c=a[0];System.out.print(b.a());}int a(){switch(c.charAt(a++)){case'(':b=0;for(int a:b())b+=a;break;case'[':b=1;for(int a:b())b*=a;}a++;return b;}List<Integer>b(){List d=new ArrayList();char c;while((c=this.c.charAt(a))!=']'&&c!=')')d.add(a());return d;}}

Expanded:

import java.util.*;

class K {
    int a =0, b;
    String c;
    public static void main(String[] a){
        K b = new K();
        b.c = a[0];
        System.out.print(b.a());
    }
    int a(){
        switch (c.charAt(a++)){
            case '(':
                b =0;
                for (int a : b())
                    b += a;
                break;
            case '[':
                b =1;
                for (int a : b())
                    b *= a;
        }
        a++;
        return b;
    }
    List<Integer> b(){
        List d = new ArrayList();
        char c;
        while ((c= this.c.charAt(a)) != ']' && c != ')')
            d.add(a());
        return d;
    }
}
Номер один
источник
2

Perl 5, 108

Сделано в качестве переводчика, а не переписывать и оценивать. Не очень хороший показ, но в любом случае интересно писать.

push@s,/[[(]/?[(ord$_&1)x2]:do{($x,$y,$z,$t)=(@{pop@s},@{pop@s});
[$t?$x*$z:$x+$z,$t]}for<>=~/./g;say$s[0][0]

Un-golfed:

# For each character in the first line of stdin
for (<> =~ /./g) {
    if ($_ eq '[' or $_ eq '(') {
        # If it's an opening...
        # ord('[') = 91 is odd, ord('(') = 40 is even
        push @stack, [ ( ord($_) & 1) x 2 ];
        # so we will push [1, 1] on the stack for brackets and [0, 0] for parens.
        # one of these is used as the flag for which operator the context is, and
        # the other is used as the initial (identity) value.
    } else {
        # otherwise, assume it's a closing
        ($top_value, $top_oper) = @{ pop @stack };
        ($next_value, $next_oper) = @{ pop @stack };
        # merge the top value with the next-to-top value according to the
        # next-to-top operator. The top operator is no longer used.
        $new_value = $next_oper
            ? $top_value * $next_value
            : $top_value + $next_value
        push @stack, [ $new_value, $next_oper ];
    }
}

say $stack[0][0]; # print the value remaining on the stack.
Hobbs
источник
2

Питон, 99

Я пробовал различные методы, но самый короткий, который я мог получить, был просто заменой и оценкой. Я был приятно удивлен, обнаружив, что могу оставить все завершающие ,элементы, так как Python может анализировать, [1,2,]а конечная запятая просто помещает все в кортеж. Только другие не просто часть будет вполне ord(c)%31%7отделить из различных символов (это имеет значение 2, 3, 1, 0для (, ), [, ]соответственно)

F=lambda s:eval(''.join(["],1),","reduce(int.__mul__,[","sum([","]),"][ord(c)%31%7]for c in s))[0]
KSab
источник
1
Это не работает как программа, не так ли? Вопрос касается программы, поэтому я не думаю, что предоставление функции соответствует требованиям. По крайней мере, это то, что люди говорили мне в прошлый раз, когда я представил функцию, когда в вопросе говорилось «программа». :)
Рето Коради
1

Ява, 301

немного другой подход, чем ответ TheNumberOne, хотя мой тоже рекурсивный по своей природе. Ввод берется из командной строки. Метод void сохраняет несколько байтов при удалении ненужных символов.

enum E{I;String n;public static void main(String[]r){I.n=r[0];System.out.print(I.e());}int e(){int v=0;if(n.charAt(0)=='('){for(s("(");n.charAt(0)!=')';)v+=e();s(")");}else if(n.charAt(0)=='['){v=1;for(s("[");n.charAt(0)!=']';)v*=e();s("]");}return v;}void s(String c){n=n.substring(1+n.indexOf(c));}}

расширен:

enum EvaluatingParenthesesAndBrackets{
    AsIntegers;
    String input;
    public static void main(String[]args){
        AsIntegers.input=args[0];
        System.out.print(AsIntegers.evaluate());
    }
    int evaluate(){
        int value=0;
        if(input.charAt(0)=='('){
            for(substringAfterChar("(");input.charAt(0)!=')';)
                value+=evaluate();
            substringAfterChar(")");
        }
        else if(input.charAt(0)=='['){
            value=1;
            for(substringAfterChar("[");input.charAt(0)!=']';)
                value*=evaluate();
            substringAfterChar("]");
        }
        return value;
    }
    void substringAfterChar(String character){
        input=input.substring(1+input.indexOf(character));
    }
}
Джек Боеприпасы
источник
1

Python, 117 110 109 байт

def C(s,p=[0]):
 m=r=s[p[0]]=='[';p[0]+=1
 while s[p[0]]in'[(':t=C(s,p);r=r*t*m+(r+t)*(1-m)
 p[0]+=1;return r

Один аспект, с которым я боролся, заключается в том, что функция в основном имеет два возвращаемых значения: произведение / сумма и новую позицию в строке. Но мне нужна функция, которая возвращает только результат, поэтому возврат кортежа не работает. Эта версия использует «ссылочный» аргумент (список с одним элементом), чтобы передать позицию обратно из функции.

У меня есть более короткая версия (103 байта), которая использует глобальную переменную для позиции. Но это будет работать только при первом звонке. И функция, которая работает только один раз, кажется немного подозрительной. Не уверен, что это будет приемлемо для кода гольф.

Алгоритм простой рекурсии. Я попробовал несколько вариантов выражения, которое обновляет продукт / сумму. Я придумал несколько версий одинаковой длины, но ни одна из них не стала короче.

Я вроде ожидал, что подход, который превращает это в выражение, которое оценивается, вероятно, победит. Но, как говорится: «Повторять - это человеческое, повторять божественное».

Рето Коради
источник
Функции теперь явно разрешены :)
Увлечения Кэлвина
@ Calvin'sHobbies У меня есть вопрос о правилах, о котором я обычно задавался вопросом, но он может возникнуть здесь: если решение реализуется как функция, означает ли это, что функцию можно вызывать более одного раза за один прогон? Например, если он использует глобальную переменную, которая правильно инициализируется только при первом вызове, это будет ... неправильно?
Рето Коради
@Retro Я бы сказал, да, это неправильно. Функция должна работать любое количество раз, не переосмысливая ее.
Увлечения Кэлвина
1

Clojure - 66 байт

Обратите внимание, что ([] (()) ([] []) [()] [([[] []] [] []) ([] [])])это действительная форма Clojure. Так:

#(letfn[(g[x](apply(if(list? x)+ *)(map g x)))](g(read-string %)))
  • Это анонимная функция, принимающая строку, читающая ее и передающая g.
  • Локальная gфункция применяется +или *к результату вызова gподэлементов своих аргументов.
  • Базовый случай рекурсии немного неуловим: он достигается xв пустой последовательности; (map g x)возвращает nilи applyвозвращает нейтральное значение для операции.
CoreDump
источник
0

JavaScript (ES6), 116 байт

s=>+[...s].reduce((t,c)=>((x=c==']')||c==')'?t[1].push(t.shift().reduce((a,b)=>x?a*b:a+b,+x)):t.unshift([]),t),[[]])
Рыбаковым
источник