Блог

Я не ищу реализацию, просто псевдокод или, по крайней мере, алгоритм для эффективной обработки этого. Мне нужно обрабатывать подобные инструкции:

 (a)     # if(a)
(a,b)   # if(a || b)
(a b)   # if(a amp;amp; b)
(a b,c) # same as ((a b),c) or if((aamp;amp;b) || c)
(a,b c) # same as (a,(b|c)) or if(a || (bamp;amp;c))
  

Таким образом, оператор имеет приоритет над , оператором. (так что мое похоже на математическое умножение с , математическим сложением, но это просто сбивает с толку).

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

1. Я просто не знаю, как решить проблему приоритета. Я мог бы, return true как только я увижу , , а предыдущее значение было true. В противном случае я повторно запущу ту же процедуру. Плюсом фактически было бы умножение bool (т. Е. true*true=true , true*false=false и т.д.).

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

    ()
   (,...
   ( ...
   (a,,...
   (a, ...
   (a ,...
   (a  ...
     

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

Конечно, у меня возникнет проблема с тем, что, возможно, придется o прочитать полный текстовый файл, если в скобках нет несоответствий, но, эй, людям следует избегать такого напряжения.

РЕДАКТИРОВАТЬ: Ах, да, я забыл ! , который также должен использоваться как классический оператор not:

 (!a b,c,!d)
  

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

Алгоритм маневровой площадки легко реализуем в относительно небольшом объеме кода. Его можно использовать для преобразования инфиксного выражения, подобного тем, что приведены в ваших примерах, в постфиксные выражения, а вычисление постфиксного выражения выполняется просто — с-большой-буквы (вам не обязательно выполнять преобразование инфикса в постфикс; вы можете напрямую вычислять постфиксный вывод маневровой станции и просто накапливать результат по ходу работы).

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

Напишите это на yacc (bison), это становится тривиальным.

 /* Yeacc Code */

%token           IDENTIFIER
%token           LITERAL

%%

Expression:      OrExpression

OrExpression:    AndExpression
            |    OrExpression ',' AndExpression

AndExpression:   NotExpression
            |    AndExpression ' ' NotExpression

NotExpression:   PrimaryExpression
            |    '!' NotExpression

PrimaryExpression: Identifier
            |    Literal
            |    '(' Expression ')'

Literal:         LITERAL
Identifier:      IDENTIFIER                          

%%        
  

Вероятно, есть лучшее (определенно, более краткое) описание этого, но я узнал, как это сделать, из этого руководства много лет назад:

http://compilers.iecc.com/crenshaw/

Это очень легко прочитать и непрограммистам (таким как я). Вам понадобятся только первые несколько глав.