Синтаксический анализатор математических выражений

[Blade]

В данном примере хочу рассмотреть программу, которая будет принимать на входе строку с математическим выражением (например 2+8*(9/4-1,5)^2) и выдавать соответствующий результат. Для анализа выражения будем использовать алгоритм рекурсивного спуска. Преимущество этого алгоритма заключается в том, что мы можем обеспечить выполнение арифметических операций в нужном порядке, в соответствии с законами математики. Наш анализатор будет состоять из нескольких функций, которые будут вызываться одна из другой. В каждой функции будут выполняться определенные арифметические действия, нам лишь необходимо вызывать функции в нужной последовательности, которую диктуют нам правила математики. Это и есть принцип алгоритма.

Разбиение строки на лексемы.
Прежде чем обрабатывать выражение, необходимо разбить его на составляющие части (лексемы). Лексема — минимальная, не делимая часть выражения. Например выражение 25+2*3 состоит из следующих лексем: 25, +, 2, *, 3.
Для разбиения выражения на лексемы напишем функцию getToken(). Данная функция будет возвращать очередную лексему из строки с указанием ее типа. В нашем случаи нам понадобится три типа: число, оператор и переменная. Оператор - это знаки +, -, *, /, %, (, ). Переменные — это латинские буквы от A до Z (Примечание: в данном примере анализатор не может обрабатывать переменные. Их обработку я рассмотрю в следующем примере, чуть позже)
И так, приступим к написанию функции getToken, вот ее код:

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

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;
}

Функция принимает указатель на обрабатываемую строку *expr. В начале функции объявлена статическая переменная i, которая хранит номер текущий позиции в анализируемой строке, далее устанавливается пустой тип лексемы (данный тип будет свидетельствовать о том, что лексем больше нет). Далее происходит проверка, не достигнут ли конец строки, и если он достигнут функция завершает свою работу. Потом с помощью библиотечной функции isspace пропускаются все разделительные символы (такие как пробел, символ табуляции и другие). Далее с помощь библиотечных функций strchr (поиск подстроки в строке), isalpha и isdigit происходит определение типа лексемы. Лексема записывается в глобальную переменную token[80], а ее тип определяется глобальным константным перечисление type. После этого функция возвращает адрес i, это необходимо, что бы обеспечить возможность обнулить эту переменную вне функции getToken().

[Blade]

После того, как мы получили возможность разбивать выражение на лексемы, мы можем приступить к его анализу. Ниже приведен полный код анализатора. Файл Parser.h

#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

[Blade]

Обратите внимание, что весь код в файле Parser.h находится между условными выражениями #ifndef и #endif, а так же определена константа #define PARSER_H_INCLUDED, это позволяет исключить повторное включение данного файла в ваш проект.
В начале подключаются необходимые библиотечные функции и объявляются прототипы всех функций. Точкой входа анализатора является функция pars(), она принимает указатель на обрабатываемую строку и присваивает его значение глобальной переменной *expr, что бы все функции могли обращаться к этой строке. Далее функция вызывает getToken() и в переменную token[80] попадает первая лексема. Потом вызывается первая из арифметических функций — fSum() и ей передается адрес переменной result, в которой в итоге будет содержаться результат вычислений.
Функция fSum() вызывает следующую — fMulti(), та в свою очередь вызывает fExp(). Когда управление переходит к функции fUnary(), она проверяет, не является ли лексема унарным плюсом или унарным минусом, если это так, функция записывает лексему (т.е. знак + или -) в переменную op и получает следующую лексему. Далее вызывается функция fBrack(), она проверяет, не является ли лексема знаком открывающийся скобки, и если это так функция рекурсивно вызывает fSum() и начинается вычисление выражения в скобках. Самой последний в цепочки вызывается функция fAtom(), она с помощью библиотечной функции atof() преобразует лексему в число типа double и записывает ее по адресу *anw, т.е. в переменную result.
Далее управление передается функциям в обратном порядке. После завершения fAtom() мы попадаем в функцию fBrack(), потом в fUnary(). Функция fUnary() проверяет, содержится ли в переменной op унарный минус, и если это необходимо, она изменяет переменную result. Далее в функции fExp() происходит обработка возведения в степени, после чего мы попадаем в функцию fMulti(), которая проверяет, является ли текущая лексема знаком умножения, деления или знаком %(остаток от деления), если необходимо, функция производит нужные подсчеты. Реализуется это следующим образом: вначале функция fMulti() записывает текущий оператор в переменную op, затем вызывается функция fExp(), которой передается адрес временной переменной temp и вся цепочка начинается сначала. После завершения цепочки управление возвращается в функцию fMulti(), а переменная temp содержит значения второго операнда для оператора, который сохранен в переменной op. После выполнения арифметических действий управление переходит к функции fSum(), которая действует аналогично функции fMulti().
После всего этого функция переменная result содержит результат вычислений. Функция pars() копирует этот результат в исходную строку, на которую указывает *expr, и работа анализатора завершается.
Теперь необходимо рассмотреть что будет, если в одной из функция произойдет ошибка, например не верное исходное выражение (20-8**3). В данном выражении два раза подряд встречается оператор умножения, следовательно анализатор не сможет обработать его. Все арифметические функции возвращает 0, если работа завершена без ошибки, и 1 если она обнаружена. При вызове каждой функции проверяется ее возвращенное значение, например

if(fMulti(anw)) return 1;

Если какая-либо функция обнаружила ошибку, она устанавливает соответствующее значение ошибки в перечислении error, и тут же завершает свою работу вернув 1. Далее по цепочки завершаются все функции, а функция pars() вместо результата копирует в обрабатываемую строку соответствующее сообщение об ошибке.

Использование анализатора.
Следующая небольшая программа демонстрирует использование анализатора. Файл parser_console.c

#include <stdio.h>
#include "parser.h"

int main(void)
{
    char expr[255]; //Содержит вычисляемое выражение
    while(1)
    {
        printf(">> ");
        gets(expr);
        if(!*expr) break; //Если введена пустая строка - завершить программу
        pars(expr); //Вычислить выражение
        printf("Result: %s\n\n", expr);
    }

    return 0;
}

Обработка выражения происходит в бесконечном цикле до тех пор, пока не будет введена пустая строка


Основа данного способа взята из книги Герберта Шилдта - Полный справочник по C

[LaptevVV]

Все хорошо, но если уж пишешь на С++, то почему не использовать тип string?
Тип стандартный, входит в любой компилятор. Работать - много удобней И НАДЕЖНЕЙ, чем с символьным массивом и указателями на символы.
Опять же, задавать максимальный размер строки - не требуется.

[Blade]

Я не писал на С++

[ds.Dante]

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

[nxt]

вот еще можно попробовать http://rus-linux.net/lib.php?name=My...acc-howto.html

удобная штука

[Ruslan-9020]

А может кто-нибудь помочь добавить в этот анализатор sin, cos, ln, exp???