superhuman: Налабал перевод выраж

Налабал перевод выражений из инфиксной формы (строки) в префиксную схемовскую, с приоритетами. Заюзал родной схемовский/рэкет парсер read - он и скобки сразу парсит.

Взял только *, +, - чтобы проще было сравнивать эвал схемовский (уже после конвертации) с эвалом питона (исходной строки через шелл-колл). С делением схема сумеет рациональные числа, а питон перейдёт на флоаты.

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

Короче, внутренняя не свёртка, а сворачивающе-рекурсивная процедура. Назвал pivot, потому что берёт оператор в середине списка, и как бы "свешивает" левый и правый список в дерево с оператором в корне, лифтит оператор, по сути.

Понятно стало, как и под правоассоциативные операторы обобщить. Те же числа, присваивающиеся в расхожих ЯП приоритетам, кажется, и не нужны вовсе: приоритеты - это упорядоченный список операций. Числа, наверное, чтобы чуть уменьшить количество проходов по выражению.

Ещё небольшие непонятки с арностью. Кажется, в обычных ЯП или унарные, или бинарные операторы только бывают. Инвалидный тернарный с++ оператор не стоит учитывать. Если оператор с 3+ операндами, то его непонятно, как записывать... кроме как функцию. Поэтому обобщать по арности такой парсер выражений и не нужно, по идее.

Но вот из нормальных может быть и вариадный, унарно-бинарный мутант. Конкретно "-" такой оказался. Вроде и легко его рассматривать как бинарный, а если внезапно пустые списки где-нибудь остаются, заменять их на 0. Так случай унарного - или + обрабатывается. Но кривовато как-то получается, вариадность не декларируется явно.

(Добавить комментарий)

	(Анонимно) 2018-02-02 15:56 (ссылка)
	почему-то постоянно путаю тебя с samozvanec, вы не братья? (Ответить) (Ветвь дискуссии)

	phantom 2018-02-02 18:33 (ссылка)
	Главное, чтоб я вас, анонимов друг с другом не путал. (Ответить) (Уровень выше) (Ветвь дискуссии)

	(Анонимно) 2018-02-03 09:54 (ссылка)
	всё так (Ответить) (Уровень выше)

	perfect_kiss 2018-02-02 23:56 (ссылка)
	ГДЕ ИСХОДНИКИ, БИЛЛИ ? (Ответить) (Ветвь дискуссии)

phantom
2018-02-03 10:06 (ссылка)

Сбрасываю "как есть". Но непонятно, зачем. Интересней самому налабать, до того как втыкать в чужие сорцы.

Модуль threading это для ~> макроса. Его надо установить через "raco pkg install threading".

#lang racket

(require threading)

; modelled after "parsers.scm"
(define (parse-via-read text)
  (define (thin-out s) (~> s string->list (add-between #\space) list->string))
  (define (envelope s) (string-append "(" s ")"))
  (~> text thin-out envelope open-input-string read))
  
(define s "1 +2 * 3 + 4*(-2-3) - 5*(6 + 3*(1-2) + 3) - 7") ; -34
;(~>> e string->list (filter-not (curry equal? #\space)))
(parse-via-read s)

(define (|evaluate python expression| s)
  (define options (string-append "-c \"print " s "\""))
  ; wtf, why does not work?
  ;(define-values (p o i e) (subprocess #f #f #f "python" options))
  ;(sleep 1) (display (read-line o)) (close-input-port o))
  (system (string-append "python " options)))
(|evaluate python expression| s)

(define precedence '(* + -))

; parentheses are already properly placed and
; recongized as sublists in the expression
(define (->prefix e)
  (define (pivot-around operation expression)
    (define (core e [accumulator '()])
      (cond [(empty? e)
             (if (empty? accumulator) 0 ; for unary - and +
                 (if (= (length accumulator) 1)
                     (car accumulator) accumulator))]
            [(list? (car e))
             (core (cdr e)
                   (cons (core (reverse (car e))) accumulator))]
            [(equal? (car e) operation)
             (list operation (core (cdr e))
                   (core '() accumulator))]
            [else (core (cdr e) (cons (car e) accumulator))]))
    ; interesting that for left associativity
    ; we have to go from right to left
    (core (reverse expression)))
  ;(foldr core '() e)) - this is for right-associativity
  ;(foldl core '() (reverse e)))... hmm need a double fold
  (foldr pivot-around e precedence))
; (pivot-around '+ e))

(->prefix (parse-via-read s))
(define-namespace-anchor anchor)
(define ns (namespace-anchor->namespace anchor))
(eval (->prefix (parse-via-read s)) ns)

(Ответить) (Уровень выше)

(Анонимно)
2018-02-03 12:07 (ссылка)

если нужно только *+- то можно проще:

минус заменяется на плюс (при этом операнд умножается на константу -1),
остаются только * и +,

и делаешь чётный и нечётный уровни вложенности
(можно больше 2х, соответственно приоритетам операторов,
можно заменить на булевы)

x+1 это [[x],[1]]
x*2 это [[x,2]]
x*2+1 это [[x,2],[1]]
-x это [[0],[-1,x]]
1+x*(2+x) это [[1],[x,[[2],[x]]]]

если модулярная арифметика, то -1 заменяешь на 2**n-1,
а деление - умножением на модулярную инверсию

форматируешь для вывода как-то так (perl):

sub format { (ref $_[0] ne ARRAY) ? $_[0] : '(' . join('+', map { join('*', map { format($_) } @{$_} ) } @{$_[0]} ) . ')'; }

(Ответить) (Ветвь дискуссии)

	(Анонимно) 2018-02-03 12:12 (ссылка)
	а оператор с 3мя операндами запиши как [x,y,z] на 3м уровне вложенности, например (Ответить) (Уровень выше)

	phantom 2018-02-04 12:43 (ссылка)
	Но зачем в такое неканоническое, мягко скажем, представление переводить? Преимущества префиксно (Ответить) (Уровень выше)

	phantom 2018-02-04 12:44 (ссылка)
	й известны, инфиксной - тоже. А что особенного у этого представления, конкретно? (Ответить) (Уровень выше) (Ветвь дискуссии)

	(Анонимно) 2018-02-04 17:46 (ссылка)
	в нём меньше избыточности, и легко раскрыть все скобки и всё упростить (Ответить) (Уровень выше) (Ветвь дискуссии)

	phantom 2018-02-05 00:39 (ссылка)
	Не согласен по всем пунктам. Что может быть проще, чем префиксная форма? Плюс представление нелегко обобщить. (Ответить) (Уровень выше)