PDA

View Full Version : Xin giúp đỡ về bài toán tính biểu thức hậu tố



nguyenmm
06-03-2007, 22:27
Yêu cầu là phải viết chương trình tính biểu thức dạn hậu tố (ví dụ: 23+4* tức là (2+3)*4 )
Source mình viết đây, nhưng chạy ko đúng mong các bạn giúp. Xin cám ơn nhiều.
<code>
#include<iostream.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
#define max 100
typedef struct{
int top;
char nodes[max];
}stack;
//kiem tra stack full
int Full(stack S)
{
if (S.top==max-1) return 1;
else return 0;
}
//kiem tra stack rong
int Empty(stack S)
{
if (S.top==-1) return 1;
else return 0;
}
//dua phan tu vao stack
void Push(int x, stack &S)
{
if (!Full(S)) S.nodes[++S.top]=x;
else cout<<"Bieu thuc qua dai (can it hon "<<max<<" ky tu)";
}
//lay ptu tu stack
char Pop(stack &S)
{
if(!Empty(S)) return S.nodes[S.top--];
else return '|';
}

void main()
{
clrscr();
stack S;
char bt[100];
int ptu,tinh,so1,so2;

cout<<"Nhap bieu thu dang hau to: ";
cin>>bt;
S.top=-1;
//
for (int i=0;i<strlen(bt);i++)
{
ptu=bt[i];
switch (ptu)
{
case '+':
{
so1=toascii(Pop(S))-toascii('0');
so2=toascii(Pop(S))-toascii('0');
tinh=so1+so2;
Push(tinh,S);
}break;
case '-':
{
so1=toascii(Pop(S))-toascii('0');
so2=toascii(Pop(S))-toascii('0');
tinh=so1-so2;
Push(tinh,S);
}break;
case '*':
{
so1=toascii(Pop(S))-toascii('0');
so2=toascii(Pop(S))-toascii('0');
tinh=so1*so2;
Push(tinh,S);
}break;
case '/':
{
so1=toascii(Pop(S))-toascii('0');
so2=toascii(Pop(S))-toascii('0');
tinh=so1/so2;
Push(tinh,S);
}break;
default:
Push(ptu,S);
}
}
cout<<"Gia tri bieu thuc la: "<<Pop(S);
getch();
}
</code>

hai_duong_dhv
05-05-2007, 11:14
Mình có 1 đoạn code chuyển biểu thức trung tố dang hậu tố và định giá biểu thức hậu tố viết bằng pascal. Mình post lên đây cho bạn tham khảo nha. Mình cũng đang cần bài này. Nếu bạn chuyển sang C rồi thì post lên cho mình với nha.

program expression;
uses crt;

{***************** Khai bao cac hang so ***********************}
const
{ Kich thuoc mang, phan tu}
SIZE_ELEMENT = 10; { Kich thuoc mot phan tu }
MAX_ELEMENT = 100; { Kich co cua mot mang }

{ Cac dinh luong }
NUM_OPERATORS = 7; { So tu hang hai ngoi }
NUM_ONE_OPERS = 1; { So toan hang mot ngoi }
NUM_FUNCS = 6; { So ham so }
NUM_CONSTANTS = 2; { So hang so }

{ Hang so toan hoc }
E = 2.718281828; { Hang so e }

{ Danh sach cac toan tu, ham, hang}
{ Danh sach toan tu hai ngoi }
OPERATOR: array [1..NUM_OPERATORS] of string[1] = ('+', '-', '*', '/', '^', '(', ')');
{ Danh sach toan tu mot ngoi }
ONE_OPER: array [1..NUM_ONE_OPERS] of string[1] = ('~');
{ Danh sach ham so }
FUNC : array [1..NUM_FUNCS] of string[SIZE_ELEMENT] = ('sin', 'cos', 'tan', 'ln', 'exp', 'abs');
{ Danh sach hang so }
CONSTANT: array [1..NUM_CONSTANTS] of string[SIZE_ELEMENT] = ('PI', 'E');

{ Ma loi }
NO_ERROR = 0; { Khong co loi }
DIVISION_BY_ZERO = 1; { Chia cho 0 }
UNDEFINE_EXPR = 2; { Khong xac dinh bieu thuc }
MATH_ERROR = 4; { Loi toan hoc }

{***************** Khai bao cac dinh dang *********************}
type
{ Kieu phan tu cua stack }
TypeOfStrStack = String[SIZE_ELEMENT];
TypeOfRealStack = real;

{ Kieu cua stack chua bieu thuc}
StrStack = record
Info: array[1..MAX_ELEMENT] of TypeOfStrStack;
Ptr: integer;
end;

{ Kieu cua stack chua gia tri cua bieu thuc}
RealStack = record
Info: array[1..MAX_ELEMENT] of TypeOfRealStack;
Ptr: integer;
end;

{***************** Khai bao cac bien **********************}
var
Expr : String; { Chua bieu thuc nhap vao }
SuffixExpr : StrStack; { Chua bieu thuc hau to }
i, ErrorCode : integer; { Bien dem va ma loi }
ValueExpr : real; { Gia tri cua bieu thuc }

{***************** Cac ham tren stack *********************}
{
Ten ham: ResetStrStack
Chuc nang: Khoi tao StrStack
Vao: Stack can khoi tao lai
}
procedure ResetStrStack(var StrStack: StrStack);
begin
StrStack.Ptr := 0;
end;

{
Ten ham: isEmptyStrStack
Chuc nang: Kiem tra stack co rong khong
Vao: Stack kiem tra
Ra: TRUE neu stack rong
}
function isEmptyStrStack(StrStack: StrStack): boolean;
begin
isEmptyStrStack := (StrStack.Ptr = 0);
end;

{
Ten ham: isFullStrStack
Chuc nang: Kiem tra stack co day khong
Vao: Stack kiem tra
Ra: TRUE neu stack day
}
function isFullStrStack(StrStack: StrStack): boolean;
begin
isFullStrStack := (StrStack.Ptr = MAX_ELEMENT);
end;

{
Ham: PushStrStack.
Chuc nang: day mot phan tu vao stack.
Vao: StrStack va Str la mot xau can day vao.
Ra: TRUE neu thuc hien thanh cong.
}
function PushStrStack(var StrStack: StrStack; Str: TypeOfStrStack): boolean;
var
FullStack: boolean;
begin
FullStack := isFullStrStack(StrStack);
if not FullStack then begin
StrStack.Ptr := StrStack.Ptr + 1;
StrStack.Info[StrStack.ptr] := Str;
end;
PushStrStack := FullStack;
end;

{
Ham: PopStrStack.
Chuc nang: lay mot phan tu tu stack.
Vao: StrStack va Str la xau nhan gia tri tu stack ra.
Ra: TRUE neu thuc hien thanh cong.
}
function PopStrStack(var StrStack: StrStack; var Str: TypeOfStrStack): boolean;
var
EmptyStack: boolean;
begin
EmptyStack := isEmptyStrStack(StrStack);
if not EmptyStack then begin
Str := StrStack.Info[StrStack.Ptr];
StrStack.Ptr := StrStack.Ptr - 1;
end;
PopStrStack := NOT EmptyStack;
end;

{
Ten ham: ResetRealStack
Chuc nang: Khoi tao RealStack
Vao: Stack can khoi tao lai
}
procedure ResetRealStack(var RealStack: RealStack);
begin
RealStack.Ptr := 0;
end;

{
Ten ham: isEmptyRealStack
Chuc nang: Kiem tra stack co rong khong
Vao: Stack kiem tra
Ra: TRUE neu stack rong
}
function isEmptyRealStack(RealStack: RealStack): boolean;
begin
isEmptyRealStack := (RealStack.Ptr = 0);
end;

{
Ten ham: isFullRealStack
Chuc nang: Kiem tra stack co day khong
Vao: Stack kiem tra
Ra: TRUE neu stack day
}
function isFullRealStack(RealStack: RealStack): boolean;
begin
isFullRealStack := (RealStack.Ptr = MAX_ELEMENT);
end;

{
Ham: PushRealStack.
Chuc nang: day mot phan tu vao stack.
Vao: RealStack va Real la mot xau can day vao.
Ra: TRUE neu thuc hien thanh cong.
}
function PushRealStack(var RealStack: RealStack; Real: TypeOfRealStack): boolean;
var
FullStack: boolean;
begin
FullStack := isFullRealStack(RealStack);
if not FullStack then begin
RealStack.Ptr := RealStack.Ptr + 1;
RealStack.Info[RealStack.ptr] := Real;
end;
PushRealStack := FullStack;
end;

{
Ham: PopRealStack.
Chuc nang: lay mot phan tu tu stack.
Vao: RealStack va Real la xau nhan gia tri tu stack ra.
Ra: TRUE neu thuc hien thanh cong.
}
function PopRealStack(var RealStack: RealStack; var Real: TypeOfRealStack): boolean;
var
EmptyStack: boolean;
begin
EmptyStack := isEmptyRealStack(RealStack);
if not EmptyStack then begin
Real := RealStack.Info[RealStack.Ptr];
RealStack.Ptr := RealStack.Ptr - 1;
end;
PopRealStack := NOT EmptyStack;
end;

{***************** Cac ham chuyen doi sang hau to *********************}
{
Ten ham: isOperator
Chuc nang: Xem xau Str co phai la toan tu hai ngoi khong
Vao: Xau Str chua toan tu
Ra: TRUE neu la toan tu hai ngoi
}
function isOperator(Str: String): boolean;
var
i: integer;
begin
i := 1;
while ((i <= NUM_OPERATORS) and (Str <> OPERATOR[i])) do i := i + 1;
isOperator := (i <= NUM_OPERATORS);
end;

{
Ten ham: isFunc
Chuc nang: Xem xau Str co phai la ham khong
Vao: Xau Str chua ham
Ra: TRUE neu la la ham
}
function isFunc(Str: String): boolean;
var
i: integer;
begin
i := 1;
while ((i <= NUM_FUNCS) and (Str <> FUNC[i])) do i := i + 1;
isFunc := (i <= NUM_FUNCS);
end;

{
Ten ham: isOneOperator
Chuc nang: Xem xau Str co phai la toan tu mot ngoi khong
Vao: Xau Str chua toan tu
Ra: TRUE neu la toan tu mot ngoi
}
function isOneOperator(Str: String): boolean;
var
i: integer;
begin
i := 1;
while ((i <= NUM_ONE_OPERS) and (Str <> ONE_OPER[i])) do i := i + 1;
isOneOperator := (i <= NUM_ONE_OPERS);
end;

{
Ten ham: isConstant
Chuc nang: Xem xau Str co phai la hang khong
Vao: Xau Str chua hang
Ra: TRUE neu la hang
}
function isConstant(Str: String): boolean;
var
i: integer;
begin
i := 1;
while ((i <= NUM_CONSTANTS) and (Str <> CONSTANT[i])) do i := i + 1;
isConstant := (i <= NUM_CONSTANTS);
end;

{
Ten ham: Position
Chuc nang: Xac dinh thu tu uu tien cua phep toan trong xau Str
Vao: Xau phep toan Str
Ra: Thu tu uu tien
}
function Position(Operation: TypeOfStrStack): integer;
var
Pos: integer;
begin
case Operation[1] of
'(' : Pos := 0;
'+','-' : Pos := 1;
'*','/' : Pos := 2;
'^' : Pos := 3;
else Pos := 4;
end;
Position := Pos;
end;

{
Ten ham: CompOperation
Chuc nang: So sanh thu tu uu tien cua 2 phep toan
Vao: Xau Operation1 va Operation2 chua 2 phep toan can so sanh
Ra: Neu Operation1 uu tien hon Operation2
}
function CompOperation(Operation1, Operation2 : TypeOfStrStack) : boolean;
begin
CompOperation := Position(Operation1) > Position(Operation2);
end;

{
Ten ham: StandardizeExpr
Chuc nang: Chuan hoa bieu thuc
Vao: Xau Expr chua bieu thuc can chuan hoa
Ra: TRUE neu chuan hoa duoc, FALSE neu bieu thuc khong hop le
}
function StandardizeExpr(var Expr: String): boolean;
var
i, len: integer;
begin
{Xoa bo cac dau trang}
len := length(Expr);
while Pos(' ', Expr) > 0 do delete(Expr, pos(' ', Expr), 1);

{ Ma hoa toan tu mot ngoi - thanh ~}
if Expr[1] = '-' then Expr[1] := '~';
for i:= 2 to len do
if (Expr[i] = '-') and (isOperator(Expr[i-1]) or isOneOperator(Expr[i-1])) and (Expr[i-1] <> ')')
then Expr[i]:= '~';

{ Loai bo cac dau + thua}
if Expr[1] = '+' then delete(Expr, 1, 1);
for i:= 2 to len do
if (Expr[i] = '+') and (isOperator(Expr[i-1]) or isOneOperator(Expr[i-1])) and (Expr[i-1] <> ')')
then delete(Expr, i, 1);

StandardizeExpr := TRUE;
end;

{
Ten ham: SuffixExpr
Chuc nang: Chuyen doi bieu thuc Expr da chuan hoa sang dang hau to
Vao: Xau Expr da chuan hoa, StrStack de chua bieu thuc hau to
}
procedure GetSuffixExpr(Expr: String; var ResultStack: StrStack);
var
len, i, IntTemp: integer;
StrTemp: TypeOfStrStack;
BlnTemp: boolean;
TempStack: StrStack;
begin
ResetStrStack(TempStack);
ResetStrStack(ResultStack);
len := length(Expr);
Expr := Expr + ' ';
for i := 1 to len do begin
BlnTemp := TRUE;
if isOperator(Expr[i]) then begin
case Expr[i] of
'(' : begin
PushStrStack(TempStack, '(');
end;
')' : begin
repeat
PopStrStack(TempStack, StrTemp);
if StrTemp <> '(' then PushStrStack(ResultStack, StrTemp);
until StrTemp = '(';
end;
else begin
BlnTemp := TRUE;
while BlnTemp do begin
if isEmptyStrStack(TempStack) then begin
PushStrStack(TempStack, Expr[i]);
BlnTemp := FALSE;
end
else begin
if CompOperation(Expr[i], TempStack.Info[TempStack.Ptr]) then begin
PushStrStack(TempStack, Expr[i]);
BlnTemp := FALSE;
end
else begin
PopStrStack(TempStack, StrTemp);
PushStrStack(ResultStack, StrTemp);
end;
end;
end;
end;
end;
BlnTemp := FALSE;
end;
if isOneOperator(Expr[i]) then begin
PushStrStack(TempStack, Expr[i]);
BlnTemp := FALSE;
end;
if BlnTemp then begin
IntTemp := 0;
StrTemp := '';
while not isOperator(Expr[i + IntTemp]) and not isOneOperator(Expr[i + IntTemp]) and ((i + IntTemp) <= len) do begin
StrTemp := StrTemp + Expr[i + IntTemp];
IntTemp := IntTemp + 1;
end;
if isFunc(StrTemp) then begin
if Expr[i + IntTemp] = '(' then PushStrStack(TempStack, StrTemp)
else PushStrStack(ResultStack, StrTemp + ' ')
end
else PushStrStack(ResultStack, StrTemp);
i := i + IntTemp - 1;
end;
end;
while not(isEmptyStrStack(TempStack)) do begin
PopStrStack(TempStack, StrTemp);
PushStrStack(ResultStack, StrTemp);
end;

end;

{***************** Cac ham tinh gia tri bieu thuc *********************}
{
Ten ham: GetValueOperator
Chuc nang: Tinh gia tri toan hang Var1 va Var2 voi toan tu hai ngoi Operator
Vao: Var1, Var2 la gia tri hai toan hang
Operator la xau chua toan tu hai ngoi
ErrorCode ma loi (xem phan hang so)
Ra: Gia tri tuong ung
}
function GetValueOperator(Var1, Var2: Real; Operator: char; var ErrorCode: integer): real;
var
Value: real;
begin
Value := 0;
ErrorCode := 0;
case Operator of
'+': Value := Var1 + Var2;
'-': Value := Var1 - Var2;
'*': Value := Var1 * Var2;
'/': begin
if Var2 <> 0 then Value := Var1 / Var2
else ErrorCode := DIVISION_BY_ZERO;
end;
'^': begin
if (Var1 > 0) then Value := exp(Var2 * ln(Var1))
else ErrorCode := MATH_ERROR;
end;
end;
getValueOperator := Value;
end;

{
Ten ham: GetValueFunc
Chuc nang: Tinh gia tri toan hang Var1 voi ham Func
Vao: Var1 la gia tri toan hang
Func la xau chua ham
ErrorCode ma loi (xem phan hang so)
Ra: Gia tri tuong ung
}
function GetValueFunc(Var1: Real; Func: String; var ErrorCode: integer): real;
var
Value: real;
begin
Value := 0;
ErrorCode := 0;
if Func = 'abs' then Value := abs(Var1);
if Func = 'sin' then Value := sin(Var1);
if Func = 'cos' then Value := cos(Var1);
if Func = 'exp' then Value := exp(Var1);
if Func = 'tan' then begin
if cos(Var1) <> 0 then Value := sin(Var1) / cos(Var1)
else ErrorCode := DIVISION_BY_ZERO
end;
if Func = 'ln' then begin
if Var1 > 0 then Value := ln(Var1)
else ErrorCode := MATH_ERROR;
end;
GetValueFunc := Value;
end;

{
Ten ham: GetValueConstant
Chuc nang: Tinh gia tri hang so Constant
Vao: Constant la xau chua hang so
ErrorCode ma loi (xem phan hang so)
Ra: Gia tri tuong ung
}
function GetValueConstant(Constant: String; var ErrorCode: integer): real;
var
Value: real;
begin
Value := 0;
ErrorCode := 0;
if Constant = 'PI' then Value := PI;
if Constant = 'E' then Value := E;
GetValueConstant := Value;
end;

{
Ten ham: GetValueOneOperator
Chuc nang: Tinh gia tri toan hang Var1 voi toan tu mot ngoi Operator
Vao: Var1 la gia tri cua toan hang
Operator la xau chua toan tu mot ngoi
ErrorCode ma loi (xem phan hang so)
Ra: Gia tri tuong ung
}
function GetValueOneOperator(Var1: real; Operator: char; var ErrorCode: integer): real;
var
Value: real;
begin
Value := 0;
ErrorCode := 0;
if Operator = '~' then Value := -Var1;
GetValueOneOperator := Value;
end;

{
Ten ham: GetValueExpr
Chuc nang: Tinh gia tri bieu thuc hau to SuffixExpr
Nhap gia tri cua cac bien
Vao: SuffixExpr chua bieu thuc hau to
ErrorCode ma loi (xem phan hang so)
Ra: Gia tri cua bieu thuc
}
function GetValueExpr(SuffixExpr: StrStack; var ErrorCode: integer): real;
type
ValueOfVariable = Record
Variable: String[MAX_ELEMENT];
Value: real;
end;
var
Stack: RealStack;
i, j, code, ListLength: integer;
StrTemp: String[SIZE_ELEMENT];
RealTemp1, RealTemp2: real;
ListVariable: array [1..MAX_ELEMENT] of ValueOfVariable;
begin
{ Duyet bieu thuc hau to tu trai qua phai }
ResetRealStack(Stack);
ListLength := 0;
for i := 1 to SuffixExpr.Ptr do begin
StrTemp := SuffixExpr.Info[i];
if NOT (isOperator(StrTemp) or isFunc(StrTemp) or isOneOperator(StrTemp)) then begin
val(StrTemp, RealTemp1, code);
if code <> 0 then begin
if NOT isConstant(StrTemp) then begin
j := 1;
while ((j <= ListLength) and (StrTemp <> ListVariable[j].Variable)) do j := j + 1;
if (j > ListLength) then begin
write('Nhap bien ', StrTemp, ' = ');
readln(RealTemp1);
ListLength := j;
ListVariable[j].Variable := StrTemp;
ListVariable[j].Value := RealTemp1;
end
else begin
RealTemp1 := ListVariable[j].Value;
end;
writeln;
end
else begin
RealTemp1 := GetValueConstant(StrTemp, code);
ErrorCode := ErrorCode or Code;
end;
end;
PushRealStack(Stack, RealTemp1);
end
else begin
if isOperator(StrTemp) then begin
PopRealStack(Stack, RealTemp2);
PopRealStack(Stack, RealTemp1);
PushRealStack(Stack, GetValueOperator(RealTemp1, RealTemp2, StrTemp[1], code));
ErrorCode := ErrorCode or Code;
end;
if isFunc(StrTemp) then begin
PopRealStack(Stack, RealTemp1);
PushRealStack(Stack, GetValueFunc(RealTemp1, StrTemp, code));
ErrorCode := ErrorCode or Code;
end;
if isOneOperator(StrTemp) then begin
PopRealStack(Stack, RealTemp1);
PushRealStack(Stack, GetValueOneOperator(RealTemp1, StrTemp[1], code));
ErrorCode := ErrorCode or Code;
end;
end;
end;
if NOT PopRealStack(Stack, RealTemp1) then RealTemp1 := 0;
GetValueExpr := RealTemp1;
end;

begin
clrscr;
{ Dua ra cac thong bao }
textcolor(white);
writeln('***************************************** ****************');
writeln(' Chuong trinh chuyen doi bieu thuc ');
writeln(' trung to sang dang hau to ');
writeln(' va tinh gia tri bieu thuc do. ');
writeln('***************************************** ****************');
writeln('Su dung : Nhap bieu thuc theo cac quy tac chung.');
writeln(' Ket thuc viec nhap bang ENTER ');
textcolor(yellow);
writeln;
writeln('Chu y : Phan biet chu hoa va chu thuong ');
writeln(' Toan tu mot ngoi - duoc thay bang ~ ');
writeln;
textcolor(white);
writeln('Cac chu cai : a..z, A..Z');
writeln('Cac chu so : 0..9 ');
write ('Toan tu 2 ngoi : ');
for i := 1 to NUM_OPERATORS do write(OPERATOR[i], ' ');
writeln;
write ('Toan tu 1 ngoi : ');
for i := 1 to NUM_ONE_OPERS do write(ONE_OPER[i], ' ');
writeln;
write ('Ham so : ');
for i := 1 to NUM_FUNCS do write(FUNC[i], ' ');
writeln;
write ('Hang so : ');
for i := 1 to NUM_CONSTANTS do write(CONSTANT[i], ' ');
writeln;
writeln('***************************************** ****************');
writeln;

{ Nhap noi dung bieu thuc }
write('Nhap bieu thuc : ');
readln(Expr);
writeln;
ResetStrStack(SuffixExpr);
{ Chuan hoa bieu thuc }
if StandardizeExpr(Expr) then begin
writeln('Toan tu mot ngoi ( - ) (lay doi cua toan hang) duoc chuyen thanh ( ~ )');
writeln('Bieu thuc trung to : ', Expr);
write('Bieu thuc hau to : ');
{ Tim bieu thuc hau to }
GetSuffixExpr(Expr, SuffixExpr);
{ In noi dung bieu thuc hau to }
for i := 1 to SuffixExpr.Ptr do write(SuffixExpr.Info[i], ' ');
writeln; writeln;
ErrorCode := 0;
{ Tinh gia tri cua bieu thuc hau to }
ValueExpr := GetValueExpr(SuffixExpr, ErrorCode);
{ In ket qua neu khong co loi }
if ErrorCode = NO_ERROR then writeln('Gia tri cua bieu thuc : ', ValueExpr:5:5)
else begin
{ Thong bao loi tuong ung }
writeln('Bieu thuc nhap vao co loi: ');
if (ErrorCode and DIVISION_BY_ZERO) <> 0 then writeln(' Chia cho 0');
if (ErrorCode and MATH_ERROR) <> 0 then writeln(' Loi toan hoc');
end;
end
else write('Bieu thuc trung to khong hop le.');
writeln;
readln;
end.

yencntt
05-05-2007, 21:21
//file stack.h
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>

const max=100;

// typedef int datatype;

struct stack
{ int top;
datatype data[max];
};
void init(stack &s)
{
s.top=-1;
}

int empty(stack s)
{
return (s.top==-1);
}

int full(stack s)
{
return (s.top==max-1);
}

void push(stack &s,datatype x)
{
if (full(s)) {
cout<<"Stack is Full";
exit(1);
}
s.data[++s.top]=x;

}

datatype pop(stack &s)
{
if (empty(s)) {
cout << "Stack is empty";
exit(1);
}
return s.data[s.top--];

}
//Chuong trinh chuyen Trung to sang Hau to

typedef char datatype;
#include <stdio.h>
#include <stack.h>
#include <string.h>
char m;
int la_tt(char a)
{
switch (a)
{
case '+': return 1;
case '-': return 1;
case '*': return 1;
case '/': return 1;
default : return 0;
}
}

int la_so(char a)
{
if (a>='0' && a<='9') return 1;
else return 0;
}

int uutien(char a)
{
switch (a)
{
case '(': return 0;
case '+': return 1;
case '-': return 1;
case '*': return 2;
case '/': return 2;
}
return -1;
}

void bt_hauto(char* bt_tt, char* bt_ht)
{
int l=-1;
stack s;
int n;
char d;
n=strlen(bt_tt);
init(s);

for (int i=0;i<n;i++)
{
d=bt_tt[i];

if (d=='(') push(s,d);
else
if (la_tt(d)) //( + - * /)
{
if ((uutien(d)>uutien(s.data[s.top]))||empty(s))
push(s,d);
else
{
while (uutien(s.data[s.top])>uutien(d))
{
l++;
bt_ht[l]=pop(s);
}
push(s,d);
}
}
else
if (d==')')
{
do
{
m=pop(s);
if (m!='(')
{
l++;
bt_ht[l]=m;
}
}
while (m!='(');
}
else // la toan hang (so tu 0 - 9)
{
l++;
bt_ht[l]=d;
}
}
while (!empty(s))
{
l++;
bt_ht[l]=pop(s);
}
l++;
bt_ht[l]=0;
}
char thuc_hien(int x, int y, char d)
{
float so;
switch (d)
{
case '+': so=x+y;break;
case '-': so=x-y;break;
case '*': so=x*y;break;
case '/': so=x*1.2/y;break;
}
return int(so)+ '0';
}

int tinh(char* bt_tt)
{
char btht[max];
char d;
int n,x,y;
char kq;
bt_hauto(bt_tt,btht);
n=strlen(btht);
stack s;
init(s);
for (int i=0;i<n;i++)
{
d=btht[i];
if (la_so(d)) push(s,d);
else
{
y=pop(s)-'0';
x=pop(s)-'0';
kq=thuc_hien(x,y,d);
push(s,kq);
}
}
return pop(s)-'0';
}

void main()
{
char bt_tt[max];
char bt_ht[max];
cout <<"Nhap vao bieu thuc trung to:";
cin >>bt_tt;
bt_hauto(bt_tt,bt_ht);
cout<<"Bieu thuc hau to la: "<<bt_ht;
cout<<"\nGia tri bieu thuc la: "<<tinh(bt_tt);
}

hai_duong_dhv
05-05-2007, 22:12
làm sao có thể chạy và gọi được tệp tiêu đề #include"stack.h"