Совет по созданию программы: "Синтезатор логических схем"

[Алексей_2012]

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

Ввод логического высказывания, например (с потолка)

например X1v(X2^x3)->x4

вопрос 1, как определить операнды и скобки, узнать какие операции были использованы и построить таблицу истинности?

У кого-нибудь есть рекурсивный парсер?

[MaTBeu]

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

Операнды и скобки определяются на этапе лексического анализа. Далее, на этапе синтаксического анализа, определяются выражения и подвыражения, по таблице разбора. После этого идет этап кодогенерации, в вашем случае - построение логических схем и таблицы истинности.

В университете я использовал LL(1) грамматику для построения компилятора для собственного языка программирования. Но есть и другие виды грамматик.

В общем, если нужно быстро - ищите готовые парсеры и подгоняйте свою программу под них. Если же хотите разобраться - вперед, в мир грамматик и разборов!

[Человек_Борща]

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

function calcMath(sExpr:string; vArgs:array of TVarRec; iFromPos:Integer):variant;
begin
 //Обработка выражения sExpression:string

  //ВЫчисление

  if POs(')',sExpr) then Result := 'o_O';
 if Pos('(',sExpr) > 0 then
  x := calcMath(sExpr,vArgs,Pos('(',sExpr)+1); //
end;

Встречая скобку от неё тут же начинается рекурсия для выражения в скобке, т.е. вызов себя и так до тех пор, пока не начнётся появление закрывающих скобок, т.е. закрытие выражения. Функция возвращает результат, на деле должна вернуть и позицию закр. скобки чтобы рекурсия уровнем выше не вошла в бесконечнось а "перешагнула" отработанное выражение.

Вычисления не должны происходить пока не будут отработаны все скобки, т.к. на момент обработки, о том что за скобками - математ. процессор ещё не знает.

[Алексей_2012]

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

Вообще все так запутано. Пните в нужную сторону, как перейти к построению таблиц истинности.

Эффективно ли использовать цикл от конца строки пока не открывающаяся скобка "(".

Если скобок нет, то еще один цикл на проверку операций и переменных....

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

Как всегда: что-то пишешь, а ошибка проявляетвя позже. Притом как всегда-ищу не в том месте и только потом до меня доходит то, что нужно смотреть ошибку в другой процедуре.

Сорь, оффтоп.

Всем Спасибо!

З.ы.: язык delphi7 lite. Мертвым, но рабочим грузом лежит Xe5...

[Utkin]

Эффективно ли использовать цикл от конца строки пока не открывающаяся скобка "(".

Между рекурсией и циклом разница только в точке зрения на задачу.
Я бы брал рекурсию (потому что мне так понятней, цикл использовать тоже можно).
Ну вот первоначальный пример:
X1v(X2^x3)
рассматриваем модель бинарной операции a op b
Шаг 1.
a=X1
op=v
b=(X2^x3)
Шаг 2. Пытаемся получить конкретные значения операндов a и b
a=значение из X1
b = операция (и здесь попадаем в рекурсию)
Шаг 3.
a=X2
op=^
b=x3
Шаг 4. Пытаемся получить конкретные значения операндов a и b
Шаг 5. Выполняем операцию ^
Шаг 6. Выполняем операцию v
При этом следует помнить, что в качестве op должны выступать только операции с низшим приоритетом. Унарные операции рассматриваются двумя способами - либо обрабатываются как особый случай либо преобразуются как бинарные (типа -a --> 0-a)

Если скобок нет, то еще один цикл на проверку операций и переменных....

Чем больше особых случаев тем сложней отлаживать потом, рассматривайте скобки как неотъемлемый элемент выражений (то есть считайте, что они могут встретиться в каждом выражении - это не особый случай, а такая же операция как и остальные).

[evg_m]

один из вариантов вычисления таблицы истинности

[Smitt&Wesson]

Сообщение от Человек_Борща

Встречая скобку от неё тут же начинается рекурсия для выражения в скобке, т.е. вызов себя и так до тех пор, пока не начнётся появление закрывающих скобок, т.е. закрытие выражения.

100 пудов - согласен, но совет для новичка. Перед тем, как заходить в рекурсию, нужно проверить выражение на наличие открывающих и соответствующих им, закрывающих скобок. В противном случае, прога может просто "повиснуть" (зациклится). Вообще, рекурсия, довольно опасная штука. Чуть недоглядел и на тебе - переполнение стека!

Сообщение от Utkin

Чем больше особых случаев тем сложней отлаживать потом

Не пугай человека.В формальной логике (для которой он пытается писать прогу) таких случаев, ничтожное количество, которые легко корректируются вручную.

[Алексей_2012]

Спасибо за ответы, тут в голову пришла еще одна идея..нашел парсер от обычного строкового калькулятора,

идея такая: заменить знаки +,-,*,/ на И, ИЛИ, НЕ.... или не вариант?

Вот код на С++, попытаюсь переписать на Делфи

#ifndef PARSER_H_INCLUDED
#define PARSER_H_INCLUDED

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>

int* getToken(char*); //Получает лексему из строки
void pars(char*); //Точка входа анализатора
int fSum(double*); //Обрабатывает сложение и вычитание
int fMulti(double*); //Обрабатывает умножение и деление
int fExp(double*); //Возведение в степень
int fUnary(double*); //Обработка унарных операторов
int fBrack(double*); //Обрабатывает выражение в скобках
int fAtom(double*); //Получает значение числа

char *expr; //Указатель на обрабатываемую строку
char token[80]; //Лексема
enum {Empty, Operator, Variable, Number} type; //Тип лексемы
enum {No, Syntax, Zero} error; //Значение ошибки

void pars(char *line)
{
    int *pointer;
    double result;
    error=No;
    expr=line;
    pointer=getToken(expr);
    fSum(&result);
    *pointer=0;

    switch(error)
    {
     case No:
        sprintf(expr, "%f", result);
        break;
     case Syntax:
        strcpy(expr, "Syntax error!");
        break;
     case Zero:
        strcpy(expr, "Divide by zero!");
        break;
    }
}

int* getToken(char *expr)
{
    static int i=0;
    type=Empty;

    if(expr[i]=='\0') //Если конец выражения
    {
        i=0;
        return 0;
    }
    while(isspace(expr[i])) i++; //Пропустить разделительные символы

    if(strchr("+-*/%^=()", expr[i]))
    {
        *token = expr[i];
        *(token+1) = '\0';
        type = Operator;
    }
    else if(isalpha(expr[i]))
    {
        *token = expr[i];
        *(token+1) = '\0';
        type = Variable;
    }
    else if(isdigit(expr[i]))
    {
        int j=0;
        token[j]=expr[i];
        while(isdigit(expr[i+1])||expr[i+1]=='.')
            token[++j]=expr[++i];
        token[j+1]='\0';
        type=Number;
    }
    i++;
    return &i;
}

int fSum(double *anw)
{
    char op;
    double temp;
    if(fMulti(anw)) return 1;

    while((op = *token) == '+' || op == '-')
    {
        getToken(expr);
        fMulti(&temp);
        switch(op)
        {
         case '+':
            *anw += temp;
            break;
         case '-':
            *anw -= temp;
            break;
        }
    }

return 0;
}

int fMulti(double *anw)
{
    char op;
    double temp;
    if(fExp(anw)) return 1; //Ошибка

    while((op = *token) == '*' || op == '/' || op == '%')
    {
        getToken(expr);
        if(fExp(&temp)) return 1; //Ошибка
        switch(op)
        {
         case '*':
            *anw *= temp;
            break;
         case '/':
            if(temp == 0.0)
            {
                error=Zero;
                return 1;
            }
            *anw /= temp;
            break;
         case '%':
            *anw = (int)*anw % (int)temp;
            break;
        }
    }

return 0;
}

int fExp(double *anw)
{
    double temp;
    if(fUnary(anw)) return 1; //Ошибка

    while(*token  == '^')
    {
        getToken(expr);
        if(fUnary(&temp)) return 1; //Ошибка
        *anw = pow(*anw, temp);
    }

return 0;
}

int fUnary(double *anw)
{
    char op=0;
    if(*token == '+' || *token == '-')
    {
        op = *token;
        getToken(expr);
    }
    if(fBrack(anw)) return 1; //Ошибка

    if(op == '-') *anw = -(*anw);

return 0;
}

int fBrack(double *anw)
{
    if(*token == '(')
    {
        getToken(expr);
        fSum(anw);

        if(*token != ')')
        {
            error=Syntax;
            return 1;
        }
        getToken(expr);
    }
    else
        if(fAtom(anw)) return 1; //Ошибка

return 0;
}

int fAtom(double *anw)
{
    if(type == Number)
    {
        *anw = atof(token);
        getToken(expr);
    }
    else
    {
        error=Syntax;
        return 1;
    }

return 0;
}

#endif // PARSER_H_INCLUDED

[Utkin]

Вариант. Подводный камень - приоритеты операций.
Вообще я впервые нашел грамотное и простое описание вопроса в книге Теория и практика С++ Г. Шилдта. Рекомендую к прочтению. Кстати, подробностей не помню, но код похож .

[Алексей_2012]

Извиняюсь, а как правильно описать функцию, состоящую из указателей?

Пробовал так:

function getToken(var ^string):^integer;

не получилось
на с++ так выглядит

int* getToken(char*);