数据结构习题

Question

以下是题的全部代码，如何补充并调试完成，就是用栈进行表达式求值，参考书籍数据结构（c语言版）文件名：ExpressionFunc.cpp#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#include "ExpressionFunc.h"//////////////////////////表达式的项struct SExpItem{    int                m_itemType;    int                m_operatorType;//操作符类型    double            m_itemValue;};/////////////////////////*功能：    初始化算术表达式参数：    pExp：算术表达式返回：    0：正确    其它：错误*/    int ExpressionInit(struct SExpression *pExp){    if ( pExp==NULL )        return 200;    memset(pExp, 0x00, sizeof(struct SExpression));  //memset 对数组中每一个元素赋相同的值   memset(数组名，值，sizeof（数组名）)    pExp->m_value = 0.0;//访问结构体有两种方法  一种是“ . ” 和“ -> ”操作    return 0;}/*功能：    计算算术表达式的值参数：    pExp：算术表达式        算术表达式由操作符、操作数组成        操作符：负-、加+、减-、乘*、除/、左括号(、右括号)        操作数：0--9和小数点组成的整数和小数返回：    0：正确，算术表达式的值在pExp->m_value中    其它：错误*/    int ExpressionEvaluate(struct SExpression *pExp){    while ( 1==1 )    {        //获取一个表达式项        //得到的是操作数：操作数处理        //得到的是操作符或结束符：操作符、结束符处理                    } //while 1==1    return 100;}//////////////////////////文件名：ExpressionMain.cpp#include <stdio.h>#include <stdlib.h>#include <string.h>#include "ExpressionFunc.h"char            *g_validChars="0123456789.+-*/()";int main(){    struct SExpression    exp;    int                    ret, ii, jj, nn, mm;//ret为表达式的值，ii为下标，nn为表达式的长度，jj为表达式中每个字符串的下标，mm为有效表达式的长度    while ( 1==1 )    {        // 20.6-5*(3.5-1.0)        // (3+2)*5-10.8        // (((-3.8)))         // (((3.2)))        // (((-3+5)))         // -3+5.7        // -3        // -(3+7.6)*6        // (3.5+2.5)*(3.5-2.5)        // 3*(-5-8)        // (-5-8)*3        // (2+3*3-1+4)        //scanf()不允许表达式中有空格        ExpressionInit(&exp);        printf("expression = ");        scanf("%s", exp.m_expStr);        //截断        exp.m_expStr[MAX_EXPRESSION_LENGTH-2]=0x00;        //结束程序?        nn=strlen(exp.m_expStr);        if ( nn<1 )            break;        if ( exp.m_expStr[0]=='#' )            break;        //检查非法字符        mm=strlen(g_validChars);        for ( ii=0;    ii<nn;    ii++ )        {            for ( jj=0;    jj<mm;    jj++ )            {                if ( exp.m_expStr[ii]==g_validChars[jj] )                     break;            }            if ( jj>=mm )             {                printf("illegal char in expression\n");                break;            }        }        if ( ii<nn )            continue;        //表达式求值        ret = ExpressionEvaluate(&exp);        if ( ret!=0 )            printf("error = %d\n", ret);        else            printf("result = %lf\n", exp.m_value);    } //1==1    return 0;}///////////////////////////文件名：ExpressionFunc.h#ifndef __EXPRESSION_FUNC_H__#define __EXPRESSION_FUNC_H__            1//表达式长度#define MAX_EXPRESSION_LENGTH        256//运算项类型#define ITEM_TYPE_NONE            0 //无#define ITEM_TYPE_OPERATOR        1 //操作符#define ITEM_TYPE_OPERAND        2 //操作数//操作符类型#define OPERATOR_TYPE_NONE        0 //无#define OPERATOR_TYPE_PLUS        1 //加#define OPERATOR_TYPE_MINUS        2 //减#define OPERATOR_TYPE_MULTIPLY    3 //乘#define OPERATOR_TYPE_DIVIDE    4 //除#define OPERATOR_TYPE_NEGATIVE    5 //负#define OPERATOR_TYPE_LEFTP        6 //左括号#define OPERATOR_TYPE_RIGHTP    7 //右括号#define OPERATOR_TYPE_END        8 //结束//最小除数#define SAMLL_NUMBER            0.000000001///////////////////////////////表达式struct SExpression{    //表达式字符串    char            m_expStr[MAX_EXPRESSION_LENGTH];    double            m_value;//值    //以下是可能的其它字段    //表达式长度    int                m_expLen;    //表达式当前位置    int                m_curPos;    //操作符堆栈    int                m_operatorStack[MAX_EXPRESSION_LENGTH];    int                m_operatorTop;    //操作数堆栈    double            m_operandStack[MAX_EXPRESSION_LENGTH];    int                m_operandTop;};/*功能：    初始化算术表达式参数：    pExp：算术表达式返回：    0：正确    其它：错误*/    int ExpressionInit(struct SExpression *pExp);    /*功能：    计算算术表达式的值参数：    pExp：算术表达式        算术表达式由操作符、操作数组成        操作符：负-、加+、减-、乘*、除/、左括号(、右括号)        操作数：0--9和小数点组成的整数和小数返回：    0：正确，算术表达式的值在pExp->m_value中    其它：错误*/    int ExpressionEvaluate(struct SExpression *pExp){    } #endif

Answer 1

One HPU kihtoner  coder。。
#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] =
{ // 运算符优先级表 
 // '+' '-' '*' '/' '(' ')' '#' '^' 
 /*'+'*/'>','>','<','<','<','>','>','<', 
 /*'-'*/'>','>','<','<','<','>','>','<', 
 /*'*'*/'>','>','>','>','<','>','>','<', 
 /*'/'*/'>','>','>','>','<','>','>','<', 
 /*'('*/'<','<','<','<','<','=',' ','<', 
 /*')'*/'>','>','>','>',' ','>','>','>', 
 /*'#'*/'<','<','<','<','<',' ','=','<', 
 /*'^'*/'>','>','>','>','<','>','>','>' 
};
typedef struct StackChar
{
 char c; 
 struct StackChar *next; 
}SC;       //StackChar类型的结点SC
typedef struct StackFloat
{
 float f; 
 struct StackFloat *next; 
}SF;       //StackFloat类型的结点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)      //计算函数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)
{ 
 // 算术表达式求值的算符优先算法
 // 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合 
 SC *OPTR=NULL;       // 运算符栈，字符元素 
 SF *OPND=NULL;       // 运算数栈，实数元素 
 char TempData[20]; 
 float Data,a,b; 
 char theta,*c,Dr[]={'#','\0'}; 
 OPTR=Push(OPTR,'#'); 
 c=strcat(MyExpression,Dr); 
 strcpy(TempData,"\0");//字符串拷贝函数 
 while (*c!= '#' || OPTR->c!='#')
 { 
  if (!In(*c, OPSET))
  { 
   Dr[0]=*c; 
   strcat(TempData,Dr);           //字符串连接函数 
   c++; 
   if (In(*c, OPSET))
   { 
    Data=atof(TempData);       //字符串转换函数(double) 
    OPND=Push(OPND, Data); 
    strcpy(TempData,"\0"); 
   } 
  } 
  else    // 不是运算符则进栈 
  {
   switch (precede(OPTR->c, *c))
   {
   case '<': // 栈顶元素优先级低 
    OPTR=Push(OPTR, *c); 
    c++; 
    break; 
   case '=': // 脱括号并接收下一字符 
    OPTR=Pop(OPTR); 
    c++; 
    break; 
   case '>': // 退栈并将运算结果入栈 
    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("请输入表达式:"); 
 gets(s);
 puts("该表达式的值为:"); 
 printf("%s\b=%g\n",s,EvaluateExpression(s));
 system("pause");
 return 0;
}

Answer 2

作业自己写吧