表达式求值(C/C++)---“栈”的一般用法

表达式求值(C/C++)---“栈”的一般用法。讲道理。数据结构每次实验都会给一个例子代码。而这个例子代码完成度每次都高达90%。我竟无言以对。上课的时候卡在C语言怎么处理字符串转整型压入栈= =。可能是太久没刷题。思维退步了太多。然后回来才想到每次乘10相加的思路。老师给的代码包含两部分,一个是CPP文件和头文件。头文件主要就是写的和栈处理相关。后文详细说吧。

0X001 seqstack头文件

该头文件主要是定义了两个类型(char,int)的结构体栈

#define Stack_Size 50

/*int栈*/
typedef struct
{
    int elem[Stack_Size]; /*用来存放栈中元素的一维数组*/
    int top;                  /*用来存放栈顶元素的下标,top为-1表示空栈*/
}IntStack;

/*char栈*/
typedef struct
{
    char elem[Stack_Size]; /*用来存放栈中元素的一维数组*/
    int top;                  /*用来存放栈顶元素的下标,top为-1表示空栈*/
}CharStack;

然后是栈的初始化就是把top值设为-1。
重要的就是栈的push进栈,pop出栈,gettop取栈顶。这里只列举一种类型的操作。

/*进栈*/
int Push(CharStack *S,char x)
{
    if(S->top==Stack_Size-1)  
        return(FALSE);  /*栈已满*/
    S->top++;
    S->elem[S->top] = x;
    return(TRUE);
}

/*出栈*/
int Pop(IntStack *S,int *x)
{  
    /* 将栈S的栈顶元素弹出,放到x所指的存储空间中 */
    if(S->top == -1)  /*栈为空*/
        return(FALSE);
    else
    {
          *x = S->elem[S->top];
        S->top--;    /* 修改栈顶指针 */
          return(TRUE);
    }
}

int GetTop(IntStack *S,int *x)
{  
    /* 将栈S的栈顶元素弹出,放到x所指的存储空间中,但栈顶指针保持不变 */
    if(S->top == -1)  /*栈为空*/
        return(FALSE);
    else
    {
          *x = S->elem[S->top];
          return(TRUE);
    }    
}

代码思路都很清晰。和操作链表类似。

0X002 cpp文件

cpp文件主要涉及的就是对操作符优先级如何去判断,如何去计算表达式。
对于判断优先级,文件采用的思路是利用一个二维数组去保存。首先先对进栈符号和运算符栈的栈顶符号做一个对比计算优先级

char Compare(char op1,char op2)
{
    //+-*/# 
    int i,j;
    switch(op1)
    {
        case '+': i=0; break;
        case '-': i=1; break;
        case '*': i=2; break;
        case '/': i=3; break;
        case '(': i=4; break;        
        case ')': i=5; break;
        case '#': i=6; break;;            
    }
    switch(op2)
    {   
        case '+': j=0; break;
        case '-': j=1; break;
        case '*': j=2; break;
        case '/': j=3; break;
        case '(': j=4; break;
        case ')': j=5; break;
        case '#': j=6; break;            
    }
    return oper[i][j];//这里的oper二维数组就是一个实现初始化好的优先级表
}

优先级表:

char oper[7][7] = {
{ '>','>','<','<','<','>','>' },
{ '>','>','<','<','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '<','<','<','<','<','=','0' },
{ '>','>','>','>','0','>','>' },
{ '<','<','<','<','<','0','=' } }; //根据运算符号的优先级对照表初始或该二位数组 
这里的0代表不可能出现的情况,=代表优先级相同即遇到括号之类。

然后就是对一个字符串表达式处理的函数

int ExpEvaluation(char str[])
/*并计算其值。 operatsign和operatdata分别为运算符栈和运算数栈, OPS为运算符集合*/
{
 char ch,topdata,topsign;
 int data,data1,data2,result; 
 int i, a, b;
 char op,tmp;
 CharStack operatsign;  //操作符栈 
 IntStack  operatdata;  //操作数栈 
 InitStack(&operatdata);
 InitStack(&operatsign); 
 
 Push(&operatsign,str[0]); //#进操作符栈 
 GetTop(&operatsign,&topsign);//获取当前操作符栈栈顶 
 i=1; 
 int num = 0; bool flag = true;
 while(str[i]!='#' || topsign!='#')   /* GetTop()通过函数值返回栈顶元素*/
 {
    while (str[i] == ' ') i++;
    if(IsNum(str[i])==1) //如果是数字字符 ,读连续的数字字符,组成操作数
    {                      
        flag = true;
        num = num * 10 + (str[i] - '0'); //字符串处理成整型变量
        i++;
        continue;
    }
    else
    {    
        if(flag==true)
        { 
            Push(&operatdata, num);
            num = 0;
            flag = false;//flag的作用防止连续遇到操作符导致前面的push一直压入num=0
        }
        switch(Compare(topsign,str[i]))//比较当前操作符合和栈顶操作符优先级 
        {
            case '<':
            {
                Push(&operatsign, str[i]);
                i++;
                break;
            } 
            case '='://脱括号并接受下一字符   
            {    
                Pop(&operatsign, &topsign);
                i++;
                break; 
            }
            case '>':              
            {
                Pop(&operatsign, &op);
                Pop(&operatdata, &b);
                Pop(&operatdata, &a);
                Push(&operatdata, Execute(a, op, b));
                //cout << a<<op<<b<<" "<<Execute(a, op, b) << endl;
                break;
            } 
        } 
    } 
    GetTop(&operatsign,&topsign);//操作符栈顶元素 
  }
   GetTop(&operatdata,&result);
   return(result);
} 

最后提供下载完成可运行的代码:http://cdn.hongxuelin.com/biaodashi.zip

添加新评论