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

Question

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

Скажем, у меня есть строка, например:

((A+B)*(C+B)) * (A+C) 

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

Так что для этой строки, я просто хочу, чтобы получить следующее:

A+B 
C+B 
(A+B)*(C+B) 
A+C 
((A+B)*(C+B)) * (A+C)  // The original String 

Любые идеи?

Answer 1

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

Давайте сохраним стек токенов (представленных в виде строк). Стек изначально пуст. Мы перебираем строку и для каждого символа, делаем следующее:

1. Если это закрывающая скобка, продолжайте выскакивать маркеры стека, пока не будет найдена открывающая скобка. Соедините все выталкиваемые маркеры (включая скобки), распечатайте результат и верните его в стек.
2. В противном случае просто нажмите маркер в стек.

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

Вот пример того, как это работает:

Пусть строка будет ((A+B)*(C+D)).

Мы продолжаем толкать токены в стек до тех пор, пока не встретится первая закрывающая скобка. В этот момент стек выглядит как [(, (, A, +, B]. Мы продолжаем выскакивать маркеры, пока не нажмем (. После их конкатенации мы получим (A+B) и вернем его обратно в стек. Состояние стека теперь [(, (A+B)]. После этого мы нажимаем токены, пока не достигнем следующего ). Стек - [(, (A+B), *, (, C, +, D]. После всплытия новое выражение равно (C+D), и стек становится [(, (A+B), *, (C+D)]. Наконец, мы доходим до последнего ) и всплываем все и получаем все выражение.

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

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