快捷導(dǎo)航

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-用棧實(shí)現(xiàn)表達(dá)式求值的方法詳解

更新時(shí)間：2013年05月24日 10:21:08 作者：

本篇文章是對(duì)在c語言中用棧實(shí)現(xiàn)表達(dá)式求值的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

1、需求分析
設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過程。利用算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值。
（1）輸入的形式：表達(dá)式，例如2*(3+4)
包含的運(yùn)算符只能有'+' 、'-' 、'*' 、'/' 、'('、 ')'；
（2）輸出的形式：運(yùn)算結(jié)果，例如2*(3+4)=14；
（3）程序所能達(dá)到的功能：對(duì)表達(dá)式求值并輸出
2、系統(tǒng)設(shè)計(jì)
1、棧的抽象數(shù)據(jù)類型定義：
ADT Stack{
數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}
約定an端為棧頂，ai端為棧底
基本操作：
Push(&S,e)
初始條件：棧S已存在
操作結(jié)果：插入元素e為新的棧頂元素
Pop(&S,&e)
初始條件：棧S已存在且非空
操作結(jié)果：刪除S的棧頂元素，并用e返回其值
}ADT Stack
3、各個(gè)模塊的主要功能：
*Push(SC *s,char c)：把字符壓棧
*Push(SF *s,float f)：把數(shù)值壓棧
*Pop(SC *s)：把字符退棧
*Pop(SF *s)：把數(shù)值退棧
Operate(a,theta,b)：根據(jù)theta對(duì)a和b進(jìn)行'+' 、'-' 、'*' 、'/' 、'^'操作
In(Test,*TestOp)：若Test為運(yùn)算符則返回true，否則返回false
ReturnOpOrd(op,*TestOp)：若Test為運(yùn)算符，則返回此運(yùn)算符在數(shù)組中的下標(biāo)
precede(Aop,Bop)：根據(jù)運(yùn)算符優(yōu)先級(jí)表返回Aop與Bop之間的優(yōu)先級(jí)
EvaluateExpression(*MyExpression)：用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值
完整的程序代碼如下：

復(fù)制代碼代碼如下:

#include"stdio.h"
#include"stdlib.h" 
#include"string.h" 
#include"math.h"
#define true 1 
#define false 0 
#define OPSETSIZE 8 
typedef int Status; 
unsigned char Prior[8][8] =
{ // 運(yùn)算符優(yōu)先級(jí)表 
 // '+' '-' '*' '/' '(' ')' '#' '^' 
 /*'+'*/'>','>','<','<','<','>','>','<', 
 /*'-'*/'>','>','<','<','<','>','>','<', 
 /*'*'*/'>','>','>','>','<','>','>','<', 
 /*'/'*/'>','>','>','>','<','>','>','<', 
 /*'('*/'<','<','<','<','<','=',' ','<', 
 /*')'*/'>','>','>','>',' ','>','>','>', 
 /*'#'*/'<','<','<','<','<',' ','=','<', 
 /*'^'*/'>','>','>','>','<','>','>','>' 
}; 
typedef struct StackChar
{
 char c; 
 struct StackChar *next; 
}SC;       //StackChar類型的結(jié)點(diǎn)SC
typedef struct StackFloat
{
 float f; 
 struct StackFloat *next; 
}SF;       //StackFloat類型的結(jié)點(diǎn)SF
SC *Push(SC *s,char c)          //SC類型的指針Push，返回p
{
 SC *p=(SC*)malloc(sizeof(SC)); 
 p->c=c; 
 p->next=s; 
 return p; 
} 
SF *Push(SF *s,float f)        //SF類型的指針Push，返回p
{
 SF *p=(SF*)malloc(sizeof(SF)); 
 p->f=f; 
 p->next=s; 
 return p; 
} 
SC *Pop(SC *s)    //SC類型的指針Pop
{
 SC *q=s; 
 s=s->next; 
 free(q); 
 return s; 
} 
SF *Pop(SF *s)      //SF類型的指針Pop
{
 SF *q=s; 
 s=s->next; 
 free(q); 
 return s; 
} 
float Operate(float a,unsigned char theta, float b)      //計(jì)算函數(shù)Operate
{
 switch(theta)
 {
 case '+': return a+b; 
 case '-': return a-b; 
 case '*': return a*b; 
 case '/': return a/b; 
 case '^': return pow(a,b); 
 default : return 0; 
 } 
} 
char OPSET[OPSETSIZE]={'+','-','*','/','(',')','#','^'}; 
Status In(char Test,char *TestOp)
{
 int Find=false; 
 for (int i=0; i< OPSETSIZE; i++)
 {
  if(Test == TestOp[i])
   Find= true; 
 } 
 return Find; 
} 
Status ReturnOpOrd(char op,char *TestOp)
{ 
 for(int i=0; i< OPSETSIZE; i++)
 {
  if (op == TestOp[i])
   return i;
 }
}
char precede(char Aop, char Bop)
{ 
 return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)]; 
} 
float EvaluateExpression(char* MyExpression)
{ 
 // 算術(shù)表達(dá)式求值的算符優(yōu)先算法
 // 設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OP為運(yùn)算符集合 
 SC *OPTR=NULL;       // 運(yùn)算符棧，字符元素 
 SF *OPND=NULL;       // 運(yùn)算數(shù)棧，實(shí)數(shù)元素 
 char TempData[20]; 
 float Data,a,b; 
 char theta,*c,Dr[]={'#','\0'}; 
 OPTR=Push(OPTR,'#'); 
 c=strcat(MyExpression,Dr); 
 strcpy(TempData,"\0");//字符串拷貝函數(shù) 
 while (*c!= '#' || OPTR->c!='#')
 { 
  if (!In(*c, OPSET))
  { 
   Dr[0]=*c; 
   strcat(TempData,Dr);           //字符串連接函數(shù) 
   c++; 
   if (In(*c, OPSET))
   { 
    Data=atof(TempData);       //字符串轉(zhuǎn)換函數(shù)(double) 
    OPND=Push(OPND, Data); 
    strcpy(TempData,"\0"); 
   } 
  } 
  else    // 不是運(yùn)算符則進(jìn)棧 
  {
   switch (precede(OPTR->c, *c))
   {
   case '<': // 棧頂元素優(yōu)先級(jí)低 
    OPTR=Push(OPTR, *c); 
    c++; 
    break; 
   case '=': // 脫括號(hào)并接收下一字符 
    OPTR=Pop(OPTR); 
    c++; 
    break; 
   case '>': // 退棧并將運(yùn)算結(jié)果入棧 
    theta=OPTR->c;OPTR=Pop(OPTR); 
    b=OPND->f;OPND=Pop(OPND); 
    a=OPND->f;OPND=Pop(OPND); 
    OPND=Push(OPND, Operate(a, theta, b)); 
    break; 
   } //switch
  } 
 } //while 
 return OPND->f; 
} //EvaluateExpression 
int main(void)
{ 
 char s[128];
 puts("請(qǐng)輸入表達(dá)式:"); 
 gets(s);
 puts("該表達(dá)式的值為:"); 
 printf("%s\b=%g\n",s,EvaluateExpression(s));
 system("pause");
 return 0;
}