Chuyển đổi biểu thức thành tổng giá trị

Xin hướng dẫn cách đổi một chuỗi dạng công thức sang số (ví dụ chuỗi (3+2)*2, sau khi biến đổi sẽ là 10).

Trả lời :

Yêu cầu của bạn thuộc dạng viết chương trình dịch. Để giải quyết tốt và tổng quát được vấn đề, trước hết bạn phải định nghĩa cú pháp được dùng để xây dựng công thức. Sau khi có cú pháp xây dựng công thức, bạn sẽ viết 2 module sau để phục vụ dịch công thức sang giá trị cuối cùng của nó:

- Module xử lý từ vựng, module này có nhiệm vụ chuyển công thức từ dạng chuỗi ký tự thô sang chuỗi token có nghĩa. Bạn có thể dùng công cụ Lex để xây dựng module này dễ dàng.
- Module xử lý cú pháp, module này có nhiệm vụ chuyển công thức từ dạng chuỗi token sang dạng cây cú pháp, nhờ đó thực hiện tính giá trị của công thức được dễ dàng. Bạn có thể dùng công cụ Yacc để xây dựng module này.

Cụ thể, nếu ta định nghĩa cú pháp của công thức ở mức đơn giản như sau:
hằngsố = chuỗi từ 1 tới n ký số thập phân
toántử = + | - | * | /
dấu ngăn = ( | )
côngthức = hằngsố
| (côngthức)
| côngthức + côngthức
| côngthức - côngthức
| côngthức * côngthức
| côngthức / côngthức
1. Ta có thể dùng ngôn ngữ đặc tả Lex để đặc tả các biểu thức chính qui miêu tả các token được dùng để xây dựng công thức như sau:

include "expr.h"

%%

[0-9]* { yylval.ival = atoi(yytext);

return ICONST; }

"*" { return MUL; }

"-" { return SUB; }

"+" { return ADD; }

"/" { return DIV; }

"(" { return LPAR; }

")" { return RPAR; }

. { }

%%

Cất đoạn lệnh trên vào file expr.l. Lưu ý rằng để hiểu và viết được các lệnh Lex đặc tả các token, bạn cần phải biết cú pháp của ngôn ngữ Lex (vốn rất dễ hiểu).

2. Soạn nội dung file expr.h như sau để phục vụ cho file expr.l ở trên:
//đoạn code C định nghĩa 1 số kiểu và hằng cần dùng

typedef union {

char* s;

int ival;

int t;

} YYSTYPE;

extern YYSTYPE yylval;

# define ICONST 257

# define ADD 258

# define SUB 259

# define DIV 260

# define MUL 261

# define LPAR 262

# define RPAR 263

3. Tương tự, ta có thể dùng ngôn ngữ đặc tả Yacc để đặc tả cú pháp của công thức và tính giá trị công thức như sau:

%{

//đoạn code C chứa các hàm dịch vụ

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

extern FILE* yyin;

char pexpr[256];

int ketqua;

void yyerror(char* ps) {

printf("%s",ps);

}

%}

%union {

char* s;

int ival;

int t;

}

%token ICONST ADD SUB DIV MUL LPAR RPAR

%type Expr ICONST

%type ADD SUB MUL DIV LPAR RPAR

%left ADD SUB

%left MUL DIV

%start Expr

%%

Expr : ICONST

{ $$ = yylval.ival; ketqua = $$;}

| LPAR Expr RPAR

{ $$ = $2; ketqua = $$;}

| Expr ADD Expr

{ $$ = $1 + $3; ketqua = $$;}

| Expr SUB Expr

{ $$ = $1 - $3; ketqua = $$;}

| Expr DIV Expr

{ $$ = $1 / $3; ketqua = $$;}

| Expr MUL Expr

{ $$ = $1 * $3; ketqua = $$;}

;

%%

//chương trình tính công thức được viết bằng C

void main(int argc, char* argv[]) {

loop:

printf("Nhập biểu thức cần tính : ");

scanf("%s",pexpr);

// Cất chuỗi ký tự miêu tả công thức lên file

remove("ftmp.txt");

yyin = fopen("ftmp.txt","w");

fprintf(yyin,"%sn",pexpr);

fclose(yyin);

// Mở lại file chứa công thức

yyin = fopen("ftmp.txt","r");

// Phân tích biểu thức và tính kết quả

yylex_init();

yyparse();

printf("Biểu thức vừa nhập có giá trị là : %dn",ketqua);

goto loop;

}

Cất đoạn lệnh trên vào file expr.y. Lưu ý rằng để hiểu và viết được các lệnh Yacc đặc tả cú pháp, bạn cần phải biết cú pháp của ngôn ngữ Yacc (vốn khá dễ hiểu).

4. Soạn đoạn script sau để dịch tự động các file ra chương trình khả thi và lưu lên file có tên là makefile:

CFLAGS= -c -g255 -v -ml -C -Ic:bc31include

LFLAGS= -ml -v -Lc:bc31lib

CC= bcc

GRAPH= c:bc31libgraphics.lib

yacc= c:Toolsfyacc

lex= c:Toolsflex

expr: expr.obj exprlex.obj

$(CC) -eexpr $(LFLAGS) expr.obj exprlex.obj

expr.obj: expr.c expr.h

$(CC) $(CFLAGS) expr.c

exprlex.obj: exprlex.c expr.h

$(CC) $(CFLAGS) exprlex.c

expr.c: expr.y

$(yacc) -vdl expr.y

del expr.c

ren ytab.c expr.c

del expr.h

ren ytab.h expr.h

exprlex.c: expr.l

$(lex) -tl expr.l >exprlex.c

Đoạn script trên sẽ dùng chương trình dịch BorlandC được cài đặt vào thư mục c:bc31, nó cũng dùng 2 tiện ích Flex và Fyacc được cài đặt ở thư mục c:Tools. (Bạn có thể tải về từ website TGVT 2 tiện ích này, với tên file lần lượt là Bison111.zip và flex251.zip).

4. Chạy tiện ích Start.All Program.Accessories.Command Prompt, nhập và thực hiện các lệnh sau:
c:>cd exprcalc
c:exprcalc>make expr
5. Sau khi biên dịch ra file chương trình có tên là expr.exe, bạn có thể chạy thử ứng dụng rồi nhập thử từng công thức cần tính và xem kết quả

Theo pcworld

Nguồn : thanglong-aptech.com

Posted in: