数据结构习题

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

作业自己写吧