Как реализовать калькулятор со скобками на си(через обратную польскую запись)?

Question

[DyudinDaniil]

Требуется реализовать калькулятор со скобками на СИ(через обратную польскую запись)
Пример:
Expression:
1+2+3
Reverse Polish Notation:
1 2 + 3 +
Result:
6

Answer 1

[Wataru]

Алгоритм сортировочной станции. Можно переключиться на английскую версию вики, там есть детальный пример, и псевдокод.

Если же от вас требуется что-то более самостоятельное, то делайте так - найдите в строке операцию с наименьшим приоритетом (ту, которая будет выполнена последней). Рекурсивно выведите обратную польскую запись для левой и правой половины, потом выводите/выполняйте операцию.

Чтобы найти операцию - проходитесь по строке, считая сколько сейчас открыто скобок. Запомните позицию самого правого встреченного "+"/"-" и "*"/"/". Если ничего не нашли - значит можно откусить внешнюю пару скобок (если скобок нет, то вся строка - число). Иначе, если есть + или - - это та самая последняя операция. Если таковой нет - то будет * или / - берите ее.

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

Comments

[Денис Загаевский]

Вот я как-то раз его кодил в универе, всё работало, но я нифига не понял, почему оно работает. Объяснения крайне скудные, и как добавить в него что-то более сложное?

[Денис Загаевский]

Алгоритм рекурсивного спуска более простой и более универсальный, закодишь один раз, и потом понятно, что делать с этим