大榕树 \ Pascal语言 \ 算法与技巧
用栈实现分数四则运算
原文链接：http://www.mydrs.org/program/list.asp?id=535
mikewu9168 ： 求助一道有关栈的题目：
利用栈实现含＋，-,*,/,(,)的算术表达式求值；
请大家帮帮忙！
bryanttjm ： 其实用递归就是用的栈，
我一直都是用递归来做表达式的。
方法是：
1、去掉两边多余的括号，如（1+2），（1×2＋3）这样子的括号，
注意，像（1＋2）＋（3＋4）这样子的括号不能去掉。
转2 2、如果就是一个数，那么计算结果就是它了，退出，否则，转3
3、找到应该最后一个运算运算符，（显然，如果有＋－号，则是从右往左第一个括号外的+－号，如果没有括号外的*/号，则是从右往左第一个×\ 号），设在第k位 4、分别递归计算k的左右两边即： 1..k-1 ， k+1..n 这两部分，设结果为s1,s2 5、根据第k位的符号，计算s1,s2 （这部分最简单，case ＋－*\ 然后计算就可以了）
bryanttjm ： 有一个 有分数计算功能的 程序 ， 你不要看其中 的 MyJia、MyJian之类的东西，
那些是进行分数计算的子程序，你只看其中带{*}的子程序，就可以了，
再把MyJia,MyJian,MyCheng,MyChu改成普通的+－*\运算，把分数用实型代替，
就成了普通的四则运算程序
{Program : ji suan a biao da shi by fen shu}
{StartTime : 14/11/2003}
{By : BryantTjm}
{FinishedTime : 14/11/2003} PROGRAM CountByFenShu; TYPE MyNumber = Record
zi : Longint ;
mu : Longint
END;
LableType = SET OF Char; CONST LableNo : ARRAY [ 1..2] OF LableType =( ['+' , '-'],['*' , '/'] ); VAR data : String;
answer : MyNumber; {*} PROCEDURE InputData; BEGIN
Writeln;
Writeln;
Writeln( 'INPUT' );
Write(' ');
Readln( data )
END; {InputData} {*} PROCEDURE GoSwap ( VAR x,y : Longint); VAR temp : Longint; BEGIN
temp := x;
x := y;
y := temp
END; {Swap} FUNCTION Gcd ( x,y : Longint) : Longint; VAR r : Longint; BEGIN
x := abs(x); y := abs(y);
While y>0 DO
BEGIN
r := x MOD y;
x := y;
y := r
END;
Gcd:=x
END; {Gcd} FUNCTION Lcm ( x,y : Longint) : Longint; BEGIN
Lcm := x * y DIV Gcd(x,y)
END; {Lcm} PROCEDURE YueFen (VAR zi,mu : Longint); VAR GcdMuZi : Longint; BEGIN
GcdMuZi := Gcd (mu,zi);
mu := mu DIV GcdMuZi;
zi := zi DIV GcdMuZi
END; {YueFen} PROCEDURE HuaJian ( VAR x : MyNumber ); BEGIN
YueFen (x.zi , x.mu)
END; {HuaJian} PROCEDURE ChangeIntegerToMyNumber ( x : Longint; Var ans : MyNumber ); BEGIN
ans.zi:=x;
ans.mu:=1
END; {ChangeInteterToMynumber} PROCEDURE MyJia ( CONST x,y : MyNumber; VAR ans : MyNumber ); VAR LcmMuXY , ForX , ForY : Longint; BEGIN
LcmMuXY := Lcm (x.mu , y.mu);
ForX := LcmMuXY DIV x.mu;
ForY := LcmMuxy DIV y.mu;
ans.mu := LcmMuXy;
ans.zi := x.zi * ForX + y.zi * ForY;
HuaJian (ans)
END; {MyJia} PROCEDURE MyJian ( x,y : MyNumber; VAR ans : MyNumber ); BEGIN
y.zi := - y.zi;
MyJia ( x , y, ans )
END; { MyJian } PROCEDURE MyCheng ( x,y : MyNumber; VAR ans : MyNumber ); BEGIN
YueFen (x.zi , y.mu);
YueFen (y.zi , x.mu);
ans.mu := x.mu * y.mu;
ans.zi := x.zi * y.zi;
HuaJian ( ans )
END; {MyCheng} PROCEDURE MyChu ( x,y : MyNumber; VAR ans : MyNumber ); BEGIN
GoSwap ( y.zi , y.mu );
MyCheng ( x , y, ans)
END; {MyChu} {*} FUNCTION FindTheLable ( thedata :String; x : LableType) : Byte; VAR i , long , KuoHao : Byte;
ok : Boolean; BEGIN
long := Length( thedata );
i := long;
KuoHao := 0;
ok := False;
WHILE (i >=2 ) AND Not ok DO
BEGIN
CASE thedata[i] OF
'(' : Inc ( KuoHao );
')' : Dec ( KuoHao )
ELSE IF (KuoHao=0) AND ( thedata[i] in x )
THEN ok := True
END; {CASE}
IF Not ok Then Dec(i)
END; {WHILE}
IF ok
THEN FindTheLable := i
ELSE FindTheLable := 0;
END; {FindTheLable} {*} PROCEDURE GetLeftAndRight ( Const TheData : String; Mid : Byte ;
VAR left_ans , right_ans : String);
BEGIN
left_ans := Copy ( TheData , 1 , Mid-1 );
right_ans := Copy ( TheData , Mid+1 , Length( TheData ) -1 )
END; {GetLeftAndRight} {*} PROCEDURE DeleteKuoHao ( VAR x : String ); VAR KuoHao , i , long: Byte;
OkToExit : Boolean; BEGIN
long := Length(x);
IF long<2 THEN Exit;
OkToExit := False;
KuoHao := 0;
REPEAT
i := 0;
REPEAT
Inc(i);
CASE x[i] OF
'(' : Inc ( KuoHao );
')' : Dec ( KuoHao )
END
UNTIL ( KuoHao = 0); IF i = long
THEN BEGIN
x := Copy (x,2,long-2);
dec(long,2)
END
ELSE OkToExit := true UNTIL (long<2) OR OkToExit
END; {DeleteKuoHao} {*} PROCEDURE MakeTheBiaoDaShi ( TheData : String; VAR ans : MyNumber); VAR Mid : Byte;
k : Longint; i :Integer;
LeftData , RightData : String;
LeftOut , RightOut : MyNumber; BEGIN
DeleteKuoHao ( TheData );
Mid := FindTheLable ( TheData , LableNo[1] );
IF Mid = 0 Then Mid := FindTheLable ( TheData , LableNo[2] );
IF Mid > 0
THEN BEGIN
GetLeftAndRight ( TheData , Mid , LeftData , RightData );
MakeTheBiaoDaShi ( LeftData , LeftOut );
MakeTheBiaoDaShi ( RightData , RightOut );
CASE TheData [Mid] OF
'+' : MyJia ( LeftOut , RightOut , ans );
'-' : MyJian ( LeftOut , RightOut , ans );
'*' : MyCheng ( LeftOut , RightOut , ans);
'/' : MyChu ( LeftOut , RightOut , ans)
END {CASE}
END {IF}
ELSE BEGIN
Val( TheData , k , i);
ChangeIntegerToMyNumber( k , ans)
END {ELSE}
END; {MakeTheBiaoDaShi} PROCEDURE ChangeToDaiFenShu ( CONST data : MyNumber; VAR x,y,z : Longint ); BEGIN
WITH data Do
BEGIN
x := zi DIV mu;
y := zi MOD mu;
z := mu
END END; {ChangeToDaiFenShu} {*} PROCEDURE PrintMyNumber ( x : MyNumber ); VAR i , j , k : Longint; BEGIN
write('=');
IF x.zi = 0
THEN Write(0)
ELSE BEGIN
ChangeToDaiFenShu ( x , i , j , k);
IF i<>0
THEN BEGIN
Write(i,' ');
j := Abs (j);
IF k>1 THEN Write('& ')
END; {IF}
IF k>1 THEN Write(j,'/',k)
END;
Writeln
END; {PrintMyNumber} { Main }
BEGIN
InputData;
MakeTheBiaoDaShi ( data , answer );
PrintMyNumber ( answer );
Readln
END. {Main}
作者：
来源：大榕树论坛
时间：2003-12-04上一篇：动态规划入门练习题
下一篇：Pascal中的常用数学函数
大榕树 版权所有 ©1999-2006