表达式求值(C/Delphi)

时间：2008-11-19 来源：hzg134679

#include      <windows.h>
#include      <stdio.h>
#include      <stdlib.h>
#include      <malloc.h>
#define    TRUE          1
#define    FALSE         0
#define    OK            1
#define    ERROR         0
#define    INFEASIBLE -1
#define    OVERFLOW     -2
#define    SYMBOL        1
#define    VALUE         2
typedef struct BiTNode
{
      char      symbol;                       //符号
      double    value;                        //数值
      int       type;                         //类型
      struct    BiTNode *lchild, *rchild;     //左右孩子指针
}BiTNode, *BiTree;
char symbol[4][4]={{'>', '>', '<', '<'},        //符号优先级
                     {'>', '>', '<', '<'},
                     {'>', '>', '>', '>'},
                     {'>', '>', '>', '>'}};

int sym2num(char s)                             //返回符号对应优先级矩阵位置
{
      switch(s)
      {
          case '+':     return 0;     break;
          case '-':     return 1;     break;
          case '*':     return 2;     break;
          case '/':     return 3;     break;
      }
}
char Precede(char a, char b)                    //返回符号优先级
{
      return(symbol[sym2num(a)][sym2num(b)]);
}
int InitBiTNode(BiTNode **node)                 //树结点的初始化
{
      (*node) = (BiTNode *)malloc(sizeof(BiTNode));
      if(!(*node))
      {
          printf("内存申请失败!\n");
          system("PAUSE");
          exit(ERROR);
      }
      (*node)->lchild = NULL;
      (*node)->rchild = NULL;
      return OK;
}
int IsSymbol(char c)                 //判断是否为符号
{
      if(c == '+' || c == '-' || c == '*' || c == '/')
          return TRUE;
      else
          return FALSE;
}
int IsNumber(char c)                  //判断是否为数字
{
      if(c >= '0' && c <= '9')
          return TRUE;
      else
          return FALSE;
}
double char2value(int *i, char *p)    //把字符型的数值转化成双浮点型
{
char *c = p;
int flag = 0,number;
double quan, ans = 0;
while(1)
{
    if(*c == '.')
    {
     flag++;
     number = c - p;
    }
    if(*c != '.' && !IsNumber(*c))
     break;
    c++;
}
*i += c - p;
if(flag == 0)
{
    for(quan = 1, c--; c >= p; c--, quan*=10)
    ans += (*c-'1'+1) * quan;
}
else
{
    for(c--, quan = pow(10, number - (c - p)); c >= p; c--)
    {
     if(*c == '.')
      continue;
     else
     {
      ans += (*c - '1' + 1) * quan;
      quan *= 10;
     }
    }
}
return(ans);
}
int GetValue(BiTree *VTree, int *i, char *Exp)       //得到表达式中的数值
{
      int j, brackets = 0;          //左括号减右括号的个数
      int flag = 0;                 //左右括号相等标志
      char ChildExp[100];           //子表达式
      if(Exp[(*i)] == '(')
      {
          (*i)++;
          brackets++;
          for(j = 0; Exp[(*i)] != '\0'; (*i)++, j++)
          {
              if(Exp[(*i)] == '(')
                  brackets++;       //左括号加1
              if(Exp[(*i)] == ')')
                  brackets--;       //右括号减1
              if(brackets == 0)
              {
                  flag++;           //左右括号相等跳出循环
                  break;
              }
              ChildExp[j] = Exp[(*i)];    //表达式括号中的内容给子表达式
          }
          if(flag == 0)
          {
              printf("括号配对语法错误！\n");
              system("PAUSE");
              exit(ERROR);         //表达式中没有找到匹配括号
          }
          ChildExp[j] = '\0';
          (*i)++;
          exp2tree(VTree, ChildExp);      //求子表达式树型结构
      }
      else
      {
          if(IsNumber(Exp[(*i)]))
          {
              InitBiTNode(VTree);         //数值类型结点
              (*VTree)->type = VALUE;
              (*VTree)->value = char2value(i, Exp + (*i));
          }
          else
          {
              printf("符号位置语法错误！\n");
              system("PAUSE");
              exit(ERROR);                //符号后跟数字
          }
      }
}
int GetSymbol(BiTree *STree, int *i, char *Exp)
{
      if(IsSymbol(Exp[(*i)]) == TRUE)
      {
          InitBiTNode(STree);            //符号类型结点
          (*STree)->type = SYMBOL;
          (*STree)->symbol = Exp[(*i)];
          (*i)++;
          return OK;
      }
      else if(Exp[(*i)] == '\0')
      {
          return ERROR;                  //结束标志返回失败
      }
      else
      {
          printf("数字后跟符号！\n");
          system("PAUSE");               //非符号非结束标志
          exit(ERROR);                   //数字后跟符号
      }
}

int exp2tree(BiTree *Tree, char *Exp)
{
      int i = 0, flag = 0;               //正常结束标志
      BiTree ValTree;                    //数值结点指针
      BiTree SymTree;                    //符号结点指针
      BiTree CurTree;                    //当前结点指针
      //预先存一个数值一个符号结点到树型结构便于后面的比较
      GetValue(&ValTree, &i, Exp);
      if(GetSymbol(&SymTree, &i, Exp) == OK)
      {
          SymTree->lchild = ValTree;
          *Tree = SymTree;
          CurTree = *Tree;
      }
      else
      {
          (*Tree) = ValTree;             //如果只有一个数值直接给根结点
          return OK;
      }
      for( ; Exp[i] != '\0'; )
      {
          GetValue(&ValTree, &i, Exp);
          if(GetSymbol(&SymTree, &i, Exp) == OK)
          {
              //与根结点符号比较优先级
              if(Precede((*Tree)->symbol, SymTree->symbol) == '>')
              {
                  //根结点符号优先于新插入符号
                  CurTree->rchild = ValTree;    //数值结点作为当前结点右子树
                  CurTree = SymTree;            //当前结点改为字符结点
                  CurTree->lchild = *Tree;      //根结点作为当前结点左子树
                  *Tree = SymTree;              //根结点改为字符结点
              }
              else
              {
                  //根结点符号后于新插入符号
                  SymTree->lchild = ValTree;    //数值结点作为字符结点右子树
                  CurTree->rchild = SymTree;    //字符结点作为当前结点右子树
                  CurTree = CurTree->rchild;    //当前结点改为当前结点右子树
              }
          }
          else
          {
              CurTree->rchild = ValTree;      //数值结点作为当前结点右子树
              flag++;                         //在数值后没有接受到符号
              return OK;                      //正常结束
          }
      }
      if(flag == 0)
      {
          printf("符号后缺数值！\n");
          system("PAUSE");
          exit(ERROR);                        //没有正常结束
      }
}

//计算一个结点的值.
double EvaluateExpression(BiTree Tree)
{
      if(Tree->type != VALUE)             //如果根结点不为数值类型
      {
          Tree->type = VALUE;             //以根结点为树型结构求值
          switch(Tree->symbol)
          {
              case '+':
                  Tree->value = EvaluateExpression(Tree->lchild) + EvaluateExpression(Tree->rchild);
                  break;
              case '-':
                  Tree->value = EvaluateExpression(Tree->lchild) - EvaluateExpression(Tree->rchild);
                  break;
              case '*':
                  Tree->value = EvaluateExpression(Tree->lchild) * EvaluateExpression(Tree->rchild);
                  break;
              case '/':
                  Tree->value = EvaluateExpression(Tree->lchild) / EvaluateExpression(Tree->rchild);
                  break;
          }
          free(Tree->lchild);             //释放左子树
          free(Tree->rchild);             //释放右子树
      }
      return(Tree->value);                //返回根结点数值
}

int main(int argc, char *argv[])
{
      BiTree T;
      T = NULL;                           //初始化根结点
      char expression[100];               //初始化表达式
      printf("请输入表达式：");
      scanf("%s", expression);            //输入表达式
      exp2tree(&T, expression);           //将表达式转为树型结构
      printf("输出的结果是：%f\n", EvaluateExpression(T));
                                        //对树型结构求解
      system("PAUSE");
}

//后面下载的.
//后缀表达式求值
int postexpression(char *exp)
{
   stack<int> *opnd=new(stack<int>);//操作数栈
   char ch=*exp;
   int x=0,y,z,flag=FALSE;
   int result;
   while(ch!='#')
   {
       if(!Operator(ch))              //如果当前字符不是运算符
       {
           if(ch!=' ')
           {
             x=x*10+(int)(ch)-48;     //计算操作数
             flag=TRUE;
           }
           else
           {
             if(flag)opnd->push(x);   //操作数入栈
             x=0;
             flag=FALSE;
           }
       }
       else                //当前字符为运算符，两个操作数出栈，计算并将结果入栈
       {
           x=opnd->pop();
           y=opnd->pop();
           z=calc(y,ch,x);
           opnd->push(z);
       }
       ch=*(++exp);          //取下一字符
   }
   result=opnd->pop();
   return(result);
}

//初始化公式
function initexp(const  exp:string):Boolean;
var
     tmp,i,j:integer;
begin
      i:=1;
      j:=1;//将零位备用做其他用途
      tmp:=0;//记录前一个符号的位置
      while i<=Length(exp) do
      begin
           if isfh( exp[i] ) then
           begin
               if i-tmp>1 then
               begin
                   arrayexp[j].isdata:=true;  //记录数字
                   arrayexp[j].data:=StrToInt(Copy(Exp,tmp+1,i-tmp-1));
                   Inc(j);
               end;
               arrayexp[j].isdata:=False;  //记录符号
               arrayexp[j].symbol:=Exp[i];
               Inc(j);
               tmp:=i; //暂存符号
           end;
           Inc(i);
      end;
end;

//除去括号
function delbrk:Boolean;
var i,j:integer;//i:左括号  j:右括号  //最好先初始化每个数组的优先级标志
begin
   i:=1;
   j:=0;
   while arrayexp[i].symbol<>'#' do
   begin
        if arrayexp[i].symbol='(' then
        begin
             j:=j+10;//优先级
             arrayexp[i].isdata:=0;//空符号
        end;
        if arrayexp[i].symbol=')' then
        begin
             j:=j-10;//优先级
             arrayexp[i].isdata:=0;//空符号
        end;
        if arrayexp[i].isdata=2 then
           arrayexp[i].priv:=arrayexp[i].priv+j;
        Inc(i);
   end;
end;

//测试文档
procedure TForm1.Button1Click(Sender: TObject);
var x:Word;
    s:string;
    i:Integer;
begin
  {s:='+';
  if s='+' then
  ShowMessage(s); }
  //x:=Integer('-');
  //ShowMessage(Char(x));
  //Edit3.Text:= string(Edit1.Text[1]);
  //Edit3.Text:= string(Precede(Edit1.Text[1],Edit2.Text[1]));
  s:='(18-8)*(9-(10-2))*2+5#';
  initexp(s);  //初始化
  delbrk;      //除去括号
  for i:=1 to Length(arrayexp) do
  begin
    if arrayexp[i].isdata=1 then
      ShowMessage('数字:'+inttostr(arrayexp[i].data));
    if arrayexp[i].isdata=2 then
     ShowMessage('符号:'+arrayexp[i].symbol+'  符号优先级是:'+inttostr(arrayexp[i].priv));
  end;
end;

//关键记录,关于符号和数字内容
type
  aryexp=packed record
  priv:ShortInt;//优先级 ,先设计最简单的     //+ -  1   * /   2
  isdata:Integer;//1:数字  2:符号  3:空.
  case Boolean of
       true:  (data:LongInt);
       False:   (symbol:char);
end;

//取得下一个可用节点   //dir   0 left减去  1 right 加上
function getindex(i,dir:Integer):Integer;
begin
    if dir=0 then
    begin
        dec(i);
        while arrayexp[i].isdata=3 do
           dec(i);
        Result:=i;
    end;
    if dir=1 then
    begin
        inc(i);
        while arrayexp[i].isdata=3 do
           inc(i);
        Result:=i;
    end;
end;

//查找根结点
function searchrootnode(highINT,LowINT:integer):integer;
var i:Integer;
     MINpriv:integer;
begin
    MINpriv:=100;
    for i:=highINT downto LowINT do
    begin
         if (arrayexp[i].isdata=2) and (arrayexp[i].priv<MINpriv) then
         begin
            MINpriv:=arrayexp[i].priv;
            Result:=i;
         end;
    end;
    if MINpriv=100 then
    Result:=-1;
end;

//建立二叉树.
//递归过程,完全不用DELPHI只带的树功能.TREEVIEW和LIST,自己管理.
//delphi初始化的时候将INTEGER类型初始化为空,Pointer为nil.
function huzgtree(highINT,LowINT:integer):PTwotree;
var  i:Integer;
     root:PTwotree;
begin
      New(root);
      if highINT>LowINT then
      begin
        i:=searchrootnode(highINT,LowINT);
        root^.NodeExp.symbol:=arrayexp[i].symbol;
      end
      else
      begin
        i:=highINT;
        root^.NodeExp.data:=arrayexp[i].data;
        //huzgtree:=root;
        //Exit;
      end;
      if getindex(i,0)>=LowINT then
      root^.lchild:=huzgtree(getindex(i,0),LowINT);
      if getindex(i,1)<=highINT then
      root^.rchild:=huzgtree(highINT,getindex(i,1));
      huzgtree:=root;
end;