Я реализовал алгоритм перевода арифметического выражения из инфиксной в постфиксную запись и последующего вычисления, руководствуясь данной статьей.
Но более-менее ёмко реализовать проверку корректности арифметического выражения у меня не получилось. Максимум - огромные костыльные связки if-else'ов с проверкой всевозможных вариантов.
Мне кажется, проверку можно реализовать более рационально, модифицировав алгоритм перевода в постфиксную запись. Но на ум ничего так и не пришло.
Подскажите, можно ли как-то скорректировать алгоритм под проверку? Или посоветуйте любой другой вариант решения данной проблемы.
В выражении, из операторов, могут быть только +,-,*,/
, а также скобки. Но при этом, выражение с избыточным количеством скобок (например : ((1+2)*3)
) будет считаться некорректным).
Числа все целые.
Алгоритм:
Если входящий элемент число, то добавляем его в очередь (QUEUE).
Если входящий элемент оператор (+, -, *, /) то проверяем:
- Если стек (STACK) пуст или содержит левую скобку в вершине (TOP), то добавляем (PUSH) входящий оператор в стек (STACK).
- Если входящий оператор имеет более высокий приоритет чем вершина (TOP), поместите (PUSH) его в стек (STACK).
- Если входящий оператор имеет более низкий или равный приоритет, чем вершине (TOP), выгружаем POP в очередь (QUEUE), пока не увидите оператор с меньшим приоритетом или левую скобку на вершине (TOP), затем добавьте (PUSH) входящий оператор в стек (STACK).
Если входящий элемент является левой скобкой, поместите (PUSH) его в стек (STACK).
Если входящий элемент является правой скобкой, выгружаем стек (POP) и добавляем его элементы в очередь (QUEUE), пока не увидите левую круглую скобку. Удалите найденную скобку из стека (STACK).
В конце выражения выгрузите стек (POP) в очередь (QUEUE)