|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Krotoff 2:5020/400 13 May 2002 20:42:02
To : Alex Astafiev
Subject : Re: Парсер математических выражений
--------------------------------------------------------------------------------
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
