表达式求值.txt

VC 括号匹配 问题

最近不断有网友询问关于表达式求值的问题，其实这个问题的基本思路在编译原理（在移进-归约一节）和数据结构（在用堆栈解决算符优先算法一节）中都有详细的说明，而且书上的伪代码都很短，可见核心算法并不难。真正难的是处理各种错误的输入，虽然算符优先算法在比较算符的优先级时也提供了一定的侦错功能，但毕竟不够强大。比如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.