Re: Парсер математических выражений

From

Alexander Krotoff ()

To

Alex Astafiev

Date

2002-05-13T20:42:02Z

Area

RU.ALGORITHMS

From: krotoff@such.srcc.msu.su (Alexander Krotoff)

Alex Astafiev <Alex.Astafiev@p16.f228.n5000.z2.fidonet.org> wrote:
 AK>> Здравствуйте все!
 AK>>
 AK>> Хочу написать сабж. Какие грабли могут быть и какими алгоритмами лучше
 AK>> пользоваться?

AA> ==== Begin of вычислитель.txt ====
AA> От: Alexander Tsarev <Alexander.Tsarev@p1.f1061.n5020.z2.fidonet.org>
AA> Тема: Вычислитель
AA> Дата: 1 ноября 1999 г. 5:25

AA> Пpивет Maxim!

AA> 18 Окт 99 08:31, Maxim Razin -> Mark Shevchenko:

 MR>> Есть классический неpекypсивный алгоpитм на двyх стеках.  Устpоен он
 MR>> так:

Это адская смесь нисходящего разборщика со структурами данных
нужными для восходящего. Эту смесь лучше готовить несколько
по-другому:
+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=
From ank Wed Oct 25 18:41:53 2000
From: krotoff@such.srcc.msu.su (Alexander Krotoff)
Subject: Re: Синтаксический разбор мат. выражений
X-Comment-To: "Mike Korablin Jr." <Mike.Korablin.Jr.@p7.f2000.n5025.z2.fidonet.org>
Newsgroups: fido7.ru.algorithms
References: <972479423@p7.f2000.n5025.z2.FIDOnet.ftn>
Organization: Он знал Сашу Бло.
Mike Korablin Jr. <Mike.Korablin.Jr.@p7.f2000.n5025.z2.fidonet.org> wrote:
MKJ> Кто что подскажет по поводу субжа?

#include <algorithm>
#include <stack>
#include <memory>
#include <stdio.h>
#include <ctype.h>

struct Node {
        int op;
        Node *left, *right;
        Node (int op, Node *left=0, Node *right=0):
                op(op), left(left), right(right) {};
};

const int ID = 255;

inline int
bin_precedence (int op)
{
        switch (op) {
        case ',': return 0;
        case '=': return 1;
        case '-':
        case '+': return 2;
        case '*':
        case '/': return 3;
        default:  throw "Incorrect binary operator.";
        }
}

inline bool left_associative (int op) { return op!='='; }
inline bool unary_op (int op) { return op=='-' || op=='+'; }
inline bool primary (int op) { return op>ID; }

static Node *parse_expr (int term);
int lex ();

static Node *
unary_expr ()
{
        int l=lex();
        if (unary_op( l ))
                return new Node( l, unary_expr() );
        else if (l=='(')
                return parse_expr( ')' );
        else if (primary( l ))
                return new Node( l );
        else
                throw "Unexpected operator";
}

typedef stack< Node* > ExprStack;

static Node *
reduce (ExprStack &expr_stack, Node *last_arg, int op)
{
        int prec = op==EOF ? -1: bin_precedence( op );

        while (!expr_stack.empty()) {
                Node *prev = expr_stack.top();

                if (prec > bin_precedence( prev->op )
                 || prec == bin_precedence( prev->op )
                 && !left_associative( op ))
                        break;

                expr_stack.pop();
                prev->right = last_arg;
                last_arg = prev;
        }

        return last_arg;
}

static Node *
parse_expr (int term)
{
        ExprStack expr_stack;
        try {
                Node *last_arg = unary_expr();
                int op;
                while ((op=lex())!=term) {
                        if (op==EOF)
                                throw "Unexpected end of expression.";
                        if (op=='[')
                                last_arg = new Node(
                                        op, last_arg, parse_expr( ']' )
                                );
                        else {
                                last_arg = reduce( expr_stack, last_arg, op );
                                expr_stack.push( new Node( op, last_arg ));
                                last_arg = unary_expr();
                        }
                }
                return reduce( expr_stack, last_arg, EOF );
        } catch (...) {
                while (!expr_stack.empty()) {
                        delete expr_stack.top();
                        expr_stack.pop();
                }
                throw;
        }
}

Node *
parse_expr()
{
        try {
                return parse_expr( EOF );
        } catch (const char *msg) {
                fprintf( stderr, "%s\n", msg );
                return 0;
        }
}

int
lex()
{
        int c;

        do { c = getchar(); } while (c != EOF && isspace( c ));

        if (c==EOF)
                return c;
        else if (isalpha( c ))
                return ID+c;
        else
                return c;
}

void
print_tree (Node *p, int n=0)
{
        for (int i=0; i<n; i++)
                putchar( '\t' );
        if (p->op > ID)
                putchar( p->op-ID );
        else
                putchar( p->op );
        putchar( '\n' );

        if (p->left)
                print_tree( p->left, n+1 );
        if (p->right)
                print_tree( p->right, n+1 );
}

int
main ()
{
        Node *tree = parse_expr();
        if (tree)
                print_tree( tree );
}

--- ifmail v.2.15dev5
 * Origin: Он знал Сашу Бло. (2:5020/400)