?? 表達式求值.txt
字號:
最近不斷有網友詢問關于表達式求值的問題，其實這個問題的基本思路在編譯原理（在移進-歸約一節）和數據結構（在用堆棧解決算符優先算法一節）中都有詳細的說明，而且書上的偽代碼都很短，可見核心算法并不難。真正難的是處理各種錯誤的輸入，雖然算符優先算法在比較算符的優先級時也提供了一定的偵錯功能，但畢竟不夠強大。比如3+（）這樣的非法式子它就無法檢測出來。所以必須自己來做全面的檢測，這些問題很多。比如：括號的匹配問題、負數如何識別？2.2.3這樣非法的數怎樣識別？如何區別3+-2（非法）和3+（-2）（合法）以及3++2（非法）和3+（+2）（合法）……為了解決這些問題，我專門寫了一個函數invaild，先對表達式進行處理，能夠檢測出我能估計到的所有錯誤，為后面的計算帶來了很大的方便。
還有一個問題就是函數的處理。加入函數后，表達式的判斷更加復雜。作為一個示例，我這里只處理了sin、cos、tan、sqrt幾個函數，基本思路是將函數作為特殊運算符來對待的（嚴格來說，可以把所有的運算符作為函數處理，一元運算符是只有一個參數的函數，二元運算符有兩個參數……），為了簡單起見，我只處理了有一個參數的函數，多參數函數的處理大家可以自己來試試。
注意，表達式中出現下列情況都作為非法處理：
1、表達式中有空格、逗號等
2、出現了我定義的函數以外的函數，或者是大小寫不對（我的函數都是小寫）
3、括號不匹配
4、有諸如3++2、3+-2之類的
5、有諸如2.2.3或.3或3.之類的非法數字
6、計算結果溢出
7、除數為0
8、函數參數不是一個
下面這些情況是合法的：
1、字符集是：0-9，'a'-'z','A'-'Z'；算符集是：+、-、*、/、^、（）；函數集是sin、cos、tan、sqrt
運算優先級依次是：（）、函數、^ 、* /、+ -，所以-2^2=-4，(-2)^2=4。
2、表達式頭尾有空格
3、函數的參數是任一個合法的表達式
4、3+（-2）或-2+3或3+（-cos(0)) 等
5、其它一般學過計算機表達式的人憑常識認為是合理的式子。
下面是我自己的程序。
--------------------------------------------------------
unit Line_cal;
{$B-}
{$J-}
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls,Math;
const
Fun_NUM = 4;
OP_NUM = 8;
type
TForm1 = class(TForm)
Edit1: TEdit;
Label1: TLabel;
Button1: TButton;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
CharType = (alpha,number,left_bracket,right_bracket,dot,op,Error);
OPType = (isNum, isOP, isFun);
StringArray = array [0..FUN_NUM] of string ;
element = record
case tag:OPType of //這是為了區分棧中存放的是數還是函數還是運算符
isOP: (opsy:integer); //存放運算符的代號
isFun: (funth : integer); //存放函數的代號
isNUM: (num: single); //存放數值
end;
Tstack = class
constructor Create(size : integer);
destructor Free;
procedure push(elem : element);
function pop : element;
function gettop : element;
function isEmpty : Boolean;
function isFull : Boolean;
public
private
space : array of element;
top : integer;
stack_size : integer;
end;
function calculate(expression : string):single;
//返回表達式的值，如果有錯，會產生異常，調用者必須捕獲異常
function invalid(var expression : string):Boolean;
//檢測表達式是否有錯誤，并做了一些前期處理，返回值為FALSE表示無錯
function judge(ch : char): CharType;
// 將當前字符分為六類，返回類型
function getnext(expression : string; var start : integer):element;
//返回表達式中一個意義單元（數或運算符或函數），返回值中的tag域表示其種類
function preced(beword,curword : element):char;
//比較棧頂算符與當前算符的優先級
function operate(a:single; opsy :integer; b:single):single;overload;
//根據算符代號計算結果
function operate(funth : integer; param:single):single;overload;
//根據函數代號計算結果
function findfun(str : string; VAR Fun_key : StringArray ):integer;
//查找是否為合法函數，返回函數的代號，為0表示函數錯誤
var
Form1: TForm1;
implementation
{$R *.DFM}
const
Error_MSG : string = 'There is a error';
OP_key : string ='+-*/()^#'; //算符在此串中的位置就是它的代號
OP_set : set of char =['+','-','*','/','^'];
precead_tab : array [1..OP_NUM+1] of string[OP_NUM+1] =
('>><<<><><','>><<<><><','>>>><><><','>>>><><><',
'<<<<<=< <','>>>> >>>>','>>>><> ><','<<<<< <=<','<<<<<>>> ');
//算符間的優先關系，依次是'+-*/()^'和'#'和函數,'#'表示表達式結束，
//把函數也看成一種運算符，' '表示這兩種運算符不能連續出現
var
Fun_key : StringArray =('','sin','cos','tan','sqrt');
//下面是一個使用的簡單例子
procedure TForm1.Button1Click(Sender: TObject);
begin
try
Label1.Caption:=floattostr(calculate(Edit1.Text));
except //這里可以根據異常的種類提供更多的信息
on EZeroDivide do Label1.Caption:='除數不能為0';
else Label1.Caption:='表達式有錯誤';
end;
end;
function calculate(expression:string):single;
var
OPTR,OPND : Tstack;
curword , tmp,num1,num2 : element;
start : integer;
preorde : char;
begin
if invalid(expression) then
raise Exception.Create(Error_MSG);
OPTR:=Tstack.create(length(expression));
OPND:=Tstack.create(length(expression));
start:=1;
try
tmp.tag:=isOP;
tmp.opsy:=8; //放'#'入棧
OPTR.push(tmp);
curword:=getnext(expression,start);
while not OPTR.isEmpty do begin //下面是數據結構中的算法，不用我多說
if curword.tag=isNum then begin
OPND.push(curword);
curword:=getnext(expression,start);
end
else begin
preorde:=preced(OPTR.gettop,curword);
if preorde='<' then begin
OPTR.push(curword);
curword:=getnext(expression,start);
end
else if preorde='=' then begin
OPTR.pop;
if start<=length(expression) then curword:=getnext(expression,start);
end
else if preorde='>' then begin
tmp:=OPTR.pop;
if tmp.tag=isOP then begin
num2:=OPND.pop;
num1:=OPND.pop;
tmp.num:=operate(num1.num,tmp.opsy,num2.num);
end
else begin
num1:=OPND.pop;
tmp.num:=operate(tmp.funth,num1.num);
end;
tmp.tag:=isNum;
OPND.push(tmp);
end
else if preorde=' ' then begin
raise Exception.Create(Error_MSG);
end;
end;
end;
tmp:=OPND.pop;
finally
OPTR.Free;
OPND.Free;
end;
result:=tmp.num;
end;
constructor Tstack.Create(size : integer);
begin
top:=0;
stack_size:=size;
setlength(space,size+1);
end;
destructor Tstack.Free;
begin
top:=0;
stack_size:=0;
setlength(space,0);
end;
procedure Tstack.push(elem : element);
begin
if not isFull then begin
inc(top);
space[top]:=elem;
end
else
raise Exception.Create('Stack is full!');
end;
function Tstack.pop : element;
begin
if isEmpty then
raise Exception.Create('Stack is empty!')
else begin
result:=space[top];
dec(top);
end;
end;
function Tstack.gettop : element;
begin
if isEmpty then
raise Exception.Create('Stack is empty!')
else
result:=space[top];
end;
function Tstack.isEmpty : Boolean;
begin
result:=(top=0);
end;
function Tstack.isFull :Boolean;
begin
result:=(top>=stack_size);
end;
function invalid(var expression : string):Boolean;
var
curch,nextch : char;
Lbk_Count,dot_count,i : integer;
curstatu, nextstatu : CharType;
begin
expression:='('+trim(expression)+')#'; //加入（是為了處理負數方便
Lbk_Count:=0;
dot_count:=0;
i:=1;
curch:=expression[i];
nextch:=expression[i+1];
result:=False;
while nextch<>'#' do begin
curstatu:=judge(curch);
nextstatu:=judge(nextch);
case curstatu of //下面根據當前字符和后繼字符來判斷是否合法
alpha:
if (nextstatu<>alpha) and (nextstatu<>left_bracket) then begin
result:=True;
exit;
end
else
if dot_count>0 then dec(dot_count);
number:
if (nextstatu<>number) and (nextstatu<>dot) and (nextstatu<>op) and (nextstatu<>right_bracket)then begin
result:=True;
exit;
end;
op:
if(nextstatu<>number) and (nextstatu<>alpha) and (nextstatu<>left_bracket) then begin
result:=True;
exit;
end
else
if dot_count>0 then dec(dot_count);
left_bracket:
if(nextstatu<>number) and (nextstatu<>alpha) and (nextstatu<>left_bracket) then
if (nextch='+') or (nextch='-') then begin //如果是負數/正數把它轉換成0-/0+的形式
Insert('0',expression,i+1);
inc(Lbk_Count);
end
else begin
result:=True;
exit;
end
else begin
inc(Lbk_Count);
if dot_count>0 then dec(dot_count);
end;
right_bracket:
if (nextstatu<>op) and (nextstatu<>right_bracket) then begin
result:=True;
exit;
end
else begin
dec(Lbk_Count);
if Lbk_Count<0 then begin
result:=True;
exit;
end;
if dot_count>0 then dec(dot_count);
end;
dot:
if (nextstatu<>number) then begin
result:=True;
exit;
end
else begin
inc(dot_count);
if (dot_count>1) then begin
result:=True;
exit;
end
end;
else
begin
result:=True;
exit;
end;
end;
i:=i+1;
curch:=expression[i];
nextch:=expression[i+1];
end;
if lbk_count<>1 then result:=True;
end;
function judge(ch : char): CharType;
begin
if (ch>='0') and (ch<='9') then
result:=number
else if (ch>='a') and (ch<='z') or (ch>='A') and (ch<='Z') then
result:=alpha
else if ch in op_set then
result:=op
else if ch='(' then
result:=left_bracket
else if ch=')' then
result:=right_bracket
else if ch='.' then
result:=dot
else
result:=Error;
end;
function getnext(expression : string; var start : integer):element;
var
i, locat : integer;
tmp : element;
ch : char;
str : string[32];
begin
i:=1;
ch:=expression[start];
locat:=pos(ch,OP_key);
if locat>0 then begin
inc(start);
tmp.tag:=isOP;
tmp.opsy:=locat;
result:=tmp;
exit;
end
else if judge(ch)=alpha then begin
repeat
str[i]:=ch;
inc(start);
inc(i);
ch:=expression[start];
until judge(ch)<>alpha;
setlength(str,i-1);
locat:=findfun(str,Fun_key);
if locat>0 then begin
tmp.tag:=isFun;
tmp.funth:=locat;
result:=tmp;
exit;
end
else raise Exception.Create(Error_MSG); //發現函數不是自己定義的
end
else if judge(ch)=number then begin
repeat
str[i]:=ch;
inc(start);
inc(i);
ch:=expression[start];
until (judge(ch)<>number) and (ch<>'.');
setlength(str,i-1);
tmp.tag:=isNum;
tmp.num:=strtofloat(str);
result:=tmp;
end
else raise Exception.Create(Error_MSG);
end;
function preced(beword,curword : element):char;
var
row,col:integer;
begin
if beword.tag=isfun then row:= OP_NUM+1
else row:=beword.opsy;
if curword.tag=isfun then col:=OP_NUM+1
else col:=curword.opsy;
result:=precead_tab[row,col];
end;
function operate(a:single; opsy :integer; b:single):single;
begin
case opsy of
1: result:=a+b;
2: result:=a-b;
3: result:=a*b;
4: result:=a/b;
7: result:=power(a,b); //求a^b
else
raise Exception.Create(Error_MSG); //這個實際上可以不要
end;
end;
function operate(funth : integer; param:single):single;
begin
case funth of
1: result:=sin(param);
2: result:=cos(param);
3: result:=tan(param);
4: result:=sqrt(param);
else
raise Exception.Create(Error_MSG); //也可以不要
end;
end;
function findfun(str : string; VAR Fun_key : StringArray ):integer;
var
i:integer;
begin
Fun_key[0]:=str; //設置監視哨
i:=Fun_Num;
while (str<>Fun_key[i]) do dec(i);
result:=i;
end;
end.
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -