Соответствующая структура данных для сопоставления символов группировки?

Question

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

Например, арифметическое выражение {25 + (3 – 6) * 8} сбалансировано и его результат равен 1.

7 + 8 * 2 сбалансирован и его результат равен 23.

Однако выражение 5 + {(13 + 7)/8 - 2 * 9 не содержит соответствующих символов группировки, поэтому мы не будем вычислять его результат.

Какова наилучшая структура данных (связанный список, стек и т. Д.)?

Answer 1

Используйте стек. Первая открытая скобка должна быть первой, которая будет закрыта.

Начать с левой стороны на право выражения.

Продолжайте нажимать открывающую скобку на стек.

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

Если стопка пуста в конце, выражение сбалансировано.