Задача 6.
Дана конечная последовательность, состоящая из левых и правых скобок pазличных заданных типов. Как определить, можно ли добавить в нее цифры и знаки арифметических действий так, чтобы получилось правильное арифметическое выражение.
|
Решение задачи 6.
Идея решения основывается на использовании стека. Считывая входную последовательность скобка за скобкой, выполняются следующие действия.
1. Если очередная скобка - открывающая, то помещаем ее в стек.
2. Если очередная скобка - закрывающая, то анализируем скобку,
стоящую в вершине стека. Возможно несколько ситуаций:
а) открывающая скобка соответствует очередной закрывающей. В этом случае она выталкивается из стека, а процесс с новой входной скобкой.
б) открывающая скобка не соответствует очередной закрывающей или стек пуст. В этом случае невозможно получить правильное арифметическое выражение.
Когда все скобки входной строки обработаны, возможны 2 ситуации.
1. Стек пуст. В этом случае можно получить правильное арифметическое выражение.
2. Стек не пуст. В этом случае невозможно получить правильное арифметическое выражение.
|
