Унарный минус

[shukshin]

Добрый вечер, уважаемые посетители форума!
Вопрос у меня про обратную польскую запись для подсчета выражений и реализацию унарных операций.
Какой должен быть у унарного минуса приоритет?
Я немного путаюсь с этим, посудите сами, с одной стороны
-1^2 = -1, приоритет выше у степени, с другой
2^-1 = 1/2, приоритет выше у унарного минуса ...
или приоритет одинаковый?

[arseniiv]

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

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

[shukshin]

Сортировочной станции

-- 04.05.2014, 20:27 --

код такой вышел:

Используется синтаксис C++

Queue *rpn(char *expr)
{
  ST_ITEM *STACK;
  Queue *RPN = malloc(sizeof(Queue));
  char c;
  int i = 0, shift;
  _create(&STACK), _create_queue(RPN);
  while( expr[i] )
  {
    c = read_lex(expr + i, &shift); //считываем очередную лексему
    if(c == UNK_KEY) //если не прочиталась лексема, то все уничтожаем и выходим(поставив флажок об     ошибке)
    {
      _enqueue(RPN, NUM_KEY, 0);
      while(STACK->size != 0)
        _pop(&STACK);
      free(STACK);
      err_calc = LEX_ERR;
      return RPN;
    }
    if(c == NUM_KEY)//прочли число - записали в очередь
    {
      _enqueue(RPN, NUM_KEY, atof(expr + i));
      i += shift;
    }
    else if(is_binop_code(c))//бинарная операция
    {
      while(STACK->size != 0 && is_binop_code(STACK->key) && 
      ((is_left(c) && (c & 3) == ((STACK->key)&3)) || ((c & 3) < ((STACK->key)&3))))
      {//пока стек не пуст и на стеке есть операция, а прочитанная ассоциативна слева и приоритет такой же   как у операции на стеке или просто меньше, чем у операции на стеке
//коды операций устроены так, что приоритет - остаток деления на 4 :)
        _enqueue(RPN, STACK->key, 0);
        _pop(&STACK);
      }
      _push(&STACK, c, 0), ++i;
    }
    else if(c == LBRK_KEY)
      _push(&STACK, c, 0), ++i;
    else if(c == RBRK_KEY)
    {
      while((STACK->key) != LBRK_KEY)
      {
        _enqueue(RPN, STACK->key, 0);
        _pop(&STACK);
      }
      _pop(&STACK), ++i;
    }
  }
  while(STACK->size != 0)
  {
    _enqueue(RPN, STACK->key, 0);
    _pop(&STACK);
  }
  free(STACK);
  return RPN;
}
 

[arseniiv]

shukshin в сообщении #859015 писал(а):

Сортировочной станции

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

[shukshin]

Так вопрос-то об этом как раз, потому что я не очень понял этот момент. У меня предположение, что унарному минусу надо проставить ассоциативность справа и приоритет как у ^.

[arseniiv]

shukshin в сообщении #859032 писал(а):

Так вопрос-то об этом как раз, потому что я не очень понял этот момент.

Т. е. вы не знаете, что должна делать написанная вами программа? Интересно.

shukshin в сообщении #859032 писал(а):

У меня предположение, что унарному минусу надо проставить ассоциативность справа и приоритет как у ^.

Увы, правую ассоциативность унарному минусу проставить не получится. Как и левую, и неассоциативность. Он же унарный.

[shukshin]

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

[arseniiv]

shukshin в сообщении #859049 писал(а):

а с унарными у меня небольшие проблемы, алгоритм-то не я изобрел

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

Оказывается, в русской вики-статье почему-то «ассоциативность» используется для унарных операций. Это можно попробовать объяснить неаккуратным дополнением после перевода английской (если был перевод), т. к. в той про унарные ничего не говорится. Унарные операции могут быть префиксными или постфиксными.

[Legioner93]

shukshin в сообщении #858965 писал(а):

-1^2 = -1, приоритет выше у степени

Да. У степени выше. Это показательное выражение. У нас есть 2 варианта подсчёта. И именно приоритет операций велит сначала возводить в степень.

shukshin в сообщении #858965 писал(а):

2^-1 = 1/2, приоритет выше у унарного минуса ...

Нет, не выше. Здесь нет различных вариантов подсчётов. Поэтому выражение не показательно
Короче, вы неправильно понимаете понятие "приоритет".
Вот вы пишите на C++, значит вам известно, что в выражении a[4+5] сначала посчитается сумма, а уже потом произойдёт обращение к элементу массива по индексу. Хотя приоритет оператора [] намного выше, чем сложения. Предлагаю в качестве закрепления темы самому придумать показательное выражение, из результата вычисления которого мы можем сравнить приоритеты + и []

-- Вт май 06, 2014 17:32:22 --

По теме топика.
1 2 3 - - - можно толковать например как (-(1-(2-3)))=-2 или же как (1-(2 - (-3)))=-4
Дёшево вы эту проблему никак не решите. Если ничего не сделать, то рождается неоднозначность.
У вас есть 3 варианта, насколько я знаю.
1) Ввести отдельный знак для унарного минуса как операции. Например '~' или '!'
Я так делал.
2) Вообще отказаться от унарного минума как от операции и оставить его лишь как часть числа. Разделять случаи минуса как бинарной операции и минуса как части числа можно банально наличием пробела между минусом и операндом, который идёт после него во входном потоке. Если слитно, то это одно цельное число, а если раздельно, то это оператор и число.
На глаз случаи тоже прекрасно отличаются, "5 -4 +"=1, а "5 - 4 +"=syntax error
Правда тогда выражения типа "-(4+5)" вообще будет нельзя записать в ОПН, ну что поделать.
Так я тоже делал.
3) Разработать самому какие-то контекстные правила отличия бинарного и унарного минуса как операций. Например снова по какому-то "пробельному" символу до или после символа '-'
Так я не делал, и вообще этот вариант только сейчас придумал.

-- Вт май 06, 2014 17:37:26 --

2 и 3 случай очевидно для ситуации, когда ввод выражения в ОПН идёт юзером прям с клавиатуры. Если нет, то эти заморочки с пробелами конечно же не нужны.

[Joker_vD]

Legioner93
$-x=0-x$, унарный минус не нужен.

$[[$0 5 -$]]=-5$
$[[$0 0 5 - 4 + -$]]=1$

Но если так хочется, то можно ввести операцию $\pm$.

P.S. Интересный факт — в Haskell можно записывать функции вида $f(x)= a \mathbin\sharp x$ как (a#), а $f(x)=x \mathbin\sharp a$ — как (#a), где $\mathbin\sharp$ — бинарная операция, за исключением вычитания из константы — (-a) означает $-a$, а не $\lambda x.\;x-a$, такую функцию приходится честно писать как \x -> x - a.

[Legioner93]

Joker_vD в сообщении #859949 писал(а):

унарный минус не нужен.

Ну и я о том же. Это был нулевой вариант, я просто забыл его написать
Хотя, если выражение идёт на подсчёт прям с клавиатуры в ОПН, тут я бы всё-таки выбрал свой первый вариант (добавление нового знака), нежели ваш (через 0).
Поясню.
Если я (=пользователь) в процессе ввода выражения захочу в "вашем" калькуляторе унарно минуснуть-с, я должен поставить прямо тут знак '-', после чего стрелочкой "влево" шагать в са-а-а-а-а-амое начало, дабы шарахнуть там '0', потом снова стрелочкой "вправо" шагать в са-а-а-а-а-амый конец и там уже продолжать ввод.
А при использовании "моего" калькуляторе мне достаточно прямо тут поставить '!' или '~' или любой другой знак, забитый для унарного минуса, и спокойно продолжить ввод.

Кстати, я краем уха слышал, что ещё до моего рождения в ходу были калькуляторы, которые считали как раз в ОПН. Как там это было реализовано?

[venco]

Legioner93 в сообщении #859984 писал(а):

Кстати, я краем уха слышал, что ещё до моего рождения в ходу были калькуляторы, которые считали как раз в ОПН. Как там это было реализовано?

ЕМНИП, была специальная кнопка - изменить знак. Кстати, она и сейчас есть даже на простых калькуляторах, обозначается "+/-". А если вы попытаетесь использовать для этого обычный минус, то можете получить неправильный результат, т.к. он именно вычтет ваше число из того, что было на экране, а там мог быть и не ноль.

[arseniiv]

Joker_vD в сообщении #859949 писал(а):

такую функцию приходится честно писать как \x -> x - a

Можно ещё и swap (-) 2 (с соблюдением пробелов это на один символ короче), хотя ведь для этого есть функция subtract = flip (-) (по-моему, не такой страшный способ, если учесть частоту использования). Вы-то наверняка знаете, это для остальных.

Не понимаю, в чём такие проблемы с минусом — можно же хранить готовую польскую нотацию не в строке (которую сначала надо составить, а потом снова разбирать — ), а как последовательность (кодов) операций (и значений); местность операции определяется по коду, никаких пускающих пыль в глаза символов — MINUS, SIGN!

[Munin]

Legioner93 в сообщении #859984 писал(а):

Кстати, я краем уха слышал, что ещё до моего рождения в ходу были калькуляторы, которые считали как раз в ОПН. Как там это было реализовано?

Гуглить по "БЗ-34" (их была целая серия, а это первая модель), в интернете и подробные описания есть, и эмуляторы. Их главным достоинством была программируемость, а не ОПН, а у продвинутых моделей - даже внешние носители памяти, перезаписываемые и неперезаписываемые. И в журнале "Техника молодёжи" печатались программы, в том числе игры :-) Кнопка "+/-" на них была обозначена как "/-/".

[Legioner93]

Munin в сообщении #860071 писал(а):

Гуглить по "БЗ-34"

Это... это прекрасно!