Вычисление простых логических выражений заданных в виде строки
Задача:
Разработать программу, которая рекурсивно по заданному простому_логическому выражению, вычисляет значение этого выражения. простое_логическое::= TRUE | FALSE | NOT простое_логическое | (простое_логическое знак_операции простое_логическое). знак-операции::= AND | OR
Вопрос: Как тут действовать, ничего не получается. Пытался идти в глубь и уже от туда вычислять это выражение но тоже провал. Провал скорее всего из-за того что не понимаю как это выражение правильно вычислять.
Ответы (1 шт):
Как тут действовать
Для вычисления, удобно преобразовать выражение в обратную польскую запись. Хорошая статья на эту тему есть у Иванова Максима.
Обратная польская нотация — это форма записи математических выражений, в которой операторы расположены после своих операндов.
Например, следующее выражение:
a + b * c * d + (e - f) * (g * h + i)в обратной польской нотации записывается следующим образом:
a b c * d * + e f - g h * i + * +
Поясню как вычисляется значение в обратной польской нотации.
- возьмём пустой стек, положим в него
a,bиc; - встречаем оператор
*;- вынимаем из стека 2 значения:
b,c; - кладём результат выполнения операции опять на стек:
b*c;
- вынимаем из стека 2 значения:
- положим
dна стек; - встречаем оператор
*;- вынимаем из стека 2 значения:
b*c,d; - кладём результат выполнения операции опять на стек:
b*c*d;
- вынимаем из стека 2 значения:
- встречаем оператор
+;- вынимаем из стека 2 значения:
a,b*c*d; - кладём результат выполнения операции опять на стек:
a+b*c*d;
- вынимаем из стека 2 значения:
- положим
e,fна стек; - встречаем оператор
-;- вынимаем из стека 2 значения:
e,f; - кладём результат выполнения операции опять на стек:
e-f;
- вынимаем из стека 2 значения:
- положим
g,hна стек; - встречаем оператор
*;- вынимаем из стека 2 значения:
g,h; - кладём результат выполнения операции опять на стек:
g*h;
- вынимаем из стека 2 значения:
- положим
iна стек; - встречаем оператор
+;- вынимаем из стека 2 значения:
g*h,i; - кладём результат выполнения операции опять на стек:
g*h+i;
- вынимаем из стека 2 значения:
- встречаем оператор
*;- вынимаем из стека 2 значения:
e-f,g*h+i; - кладём результат выполнения операции опять на стек:
(e-f)*(g*h+i);
- вынимаем из стека 2 значения:
- встречаем оператор
*;- вынимаем из стека 2 значения:
a+b*c*d,(e-f)*(g*h+i); - кладём результат выполнения операции опять на стек:
a+b*c*d+(e-f)*(g*h+i);
- вынимаем из стека 2 значения:
- обратная польская нотация закончилась, результат на вершине стека.