Data structure course design detailed explanation of how to evaluate an expression using a stack

1. Demand analysis
Design a program that demonstrates the process of evaluating arithmetic expressions using operator precedence. By using operator precedence relation, the evaluation of mixed arithmetic expressions is realized.
(1) input form: expression, such as 2*(3+4)
        Contains only '+', '-', '*', '/', '(', ')';
(2) output form: operation result, such as 2*(3+4)=14;
(3) the function that the program can achieve: evaluate the expression and output
2. System design
1. Abstract data type definition of the stack:
ADT Stack {
Data object: D={ai|ai ∈ set, I =1,2... , n, n p 0}
Data relationship: R1={ < Ai ai - 1 > | - 1, ai ai ∈ D, I = 2,... , n}
                  The an end is the top of the stack and the ai end is the bottom of the stack
Basic operation:
Push (& S, e)
Initial condition: stack S already exists
Result: insert element e as the new top element
Pop (& S, & e)
Initial condition: stack S exists and is not empty
Result: remove the top element of S and return its value with e
} ADT Stack
3. Main functions of each module:
*Push(SC *s,char c) : to Push a stack of characters
*Push(SF *s,float f) : to Push a value on a stack
*Pop(SC *s) : unloads characters
*Pop(SF *s) : unloads the value
Operate (a, theta, b) : according to the a and b is on the '+', '-' and '*', '/', '^' operation
In(Test,*TestOp) : returns true if Test is operator, false otherwise
ReturnOpOrd (op, * TestOp) : if the Test for the operator, it returns the operators in the array subscript
Precede (Aop,Bop) : returns the priority between Aop and Bop based on the operator priority table
EvaluateExpression(*MyExpression) : evaluate arithmetic expressions using operator precedence
The complete program code is as follows:

#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] =
{ //Operator priority table
 // '+' '-' '*' '/' '(' ')' '#' '^' 
 '>','>','<','<','<','>','>','<', 
 '>','>','<','<','<','>','>','<', 
 '>','>','>','>','<','>','>','<', 
 /*'/'*/'>','>','>','>','<','>','>','<', 
 '<','<','<','<','<','=',' ','<', 
 '>','>','>','>',' ','>','>','>', 
 '<','<','<','<','<',' ','=','<', 
 '>','>','>','>','<','>','>','>' 
}; 
typedef struct StackChar
{
 char c; 
 struct StackChar *next; 
}SC;       //Node SC of type StackChar
typedef struct StackFloat
{
 float f; 
 struct StackFloat *next; 
}SF;       //Node SF of type StackFloat
SC *Push(SC *s,char c)          //A pointer of type SC pushes, returning p
{
 SC *p=(SC*)malloc(sizeof(SC)); 
 p->c=c; 
 p->next=s; 
 return p; 
} 
SF *Push(SF *s,float f)        //Push a pointer of type SF, returning p
{
 SF *p=(SF*)malloc(sizeof(SF)); 
 p->f=f; 
 p->next=s; 
 return p; 
} 
SC *Pop(SC *s)    //Pointer Pop of type SC
{
 SC *q=s; 
 s=s->next; 
 free(q); 
 return s; 
} 
SF *Pop(SF *s)      //Pointer Pop of type SF
{
 SF *q=s; 
 s=s->next; 
 free(q); 
 return s; 
} 
float Operate(float a,unsigned char theta, float b)      //Calculate the function operator
{
 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)
{ 
 //Operator precedence algorithm for evaluating arithmetic expressions
 //Let OPTR and OPND be operator stack and operand stack respectively, and OP be operator set
 SC *OPTR=NULL;       //Operator stack, character element
 SF *OPND=NULL;       //Operand stack, real element
 char TempData[20]; 
 float Data,a,b; 
 char theta,*c,Dr[]={'#','0'}; 
 OPTR=Push(OPTR,'#'); 
 c=strcat(MyExpression,Dr); 
 strcpy(TempData,"0");//String copy function
 while (*c!= '#' || OPTR->c!='#')
 { 
  if (!In(*c, OPSET))
  { 
   Dr[0]=*c; 
   strcat(TempData,Dr);           //String concatenation function
   c++; 
   if (In(*c, OPSET))
   { 
    Data=atof(TempData);       //String conversion function (double)
    OPND=Push(OPND, Data); 
    strcpy(TempData,"0"); 
   } 
  } 
  else    //If not, push on the stack
  {
   switch (precede(OPTR->c, *c))
   {
   case '<': //The top element of the stack has a low priority
    OPTR=Push(OPTR, *c); 
    c++; 
    break; 
   case '=': //Unbracket and receive the next character
    OPTR=Pop(OPTR); 
    c++; 
    break; 
   case '>': //Unstack and push the result of the operation
    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(" Please enter an expression :"); 
 gets(s);
 puts(" The value of this expression is :"); 
 printf("%sb=%gn",s,EvaluateExpression(s));
 system("pause");
 return 0;
}

The test results are as follows:

< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201305/201305241019054.gif ">