数据结构——表达式求值（中序）

快来打我* 2022-12-23 06:18 100阅读 0赞

## 表达式求值（中序） ##

**实验二 基于栈的中缀算术表达式求值  
【实验目的】  
1.掌握栈的基本操作算法的实现,包括栈初始化、进栈、出栈、取栈顶元素等。  
2.掌握利用栈实现中缀表达式求值的算法。  
【实验内容】  
问题描述  
输入一个中缀算术表达式,求解表达式的值。运算符包括“+”、“-”、“*”、“/”、“(”、“)”、“=”，参加运算的数为 double类型且为正数。(要求:直接使用中缀算术表达式进行计算,不能转换为后缀或前缀表达式再进行计算,只考虑二元运算即可。)  
输入要求  
多组数据,每组数据一行,对应一个算术表达式,每个表达式均以“=”结尾。当表达式只有一个“=”时,输入结束。参加运算的数为 double类型。  
输出要求  
对于每组数据输出1行,为表达式的运算结果。输出保留两位小数。  
输入样例  
2+2=  
20*(4.5-3)=  
输出样例  
4.00  
30.00  
【实验提示】  
此实验内容即为教材（P53）算法3.4的扩展内容,算法3.4只考虑个位数的运算,不具备拼数功能。拼数功能可以手工编写,也可以借助C语言的库函数atof()函数来完成,其功能是将字符串转换为双精度浮点数( double)。**

# 解决问题的核心思路： #

为实现算符优先算法，可以使用两个工作栈：  
1.一个称为OPTR，用于寄存运算符  
2.另一个称做OPND，用于寄存操作数或运算结果  
算法的基本思想：  
（1）：首先置操作数栈为空栈，表达式的起始符“=”为运算符栈的栈底元素；  
（2）：依次读入表达式中的每一个字符：  
若是操作数则进OPND栈，若是运算符则和OPND栈的栈顶运算符比较  
若栈顶运算符<运算符c：运算符c进栈OPND  
若栈顶运算符=运算符c：（此时栈顶运算符为“（”，运算符c为”）”）  
若栈顶运算符>运算符c：将栈顶运算符出栈，进行运算  
（3）直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“=”）。

### 完成这个问题需要的知识前提：栈 ###

知识前提：栈的基本运算  
顺序栈

#include<stdio.h>
    #include<bits/stdc++.h>
    using namespace std;
    
    
    typedef int Status;
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    
    // ------栈的顺序存储结构表示----------
    #define STACK_INIT_SIZE 100 	// 存储空间初始分配量
    #define STACK_INCREMENT 10 	// 存储空间分配增量
    typedef int  ElemType;
    typedef struct {
        
      ElemType *base; 	// 栈底指针
      ElemType *top; 	// 栈顶指针
      int stacksize; 	// 栈空间大小
    } SqStack;
    
    
    void InitStack(SqStack &S)
    {
        
        // 构造一个空栈S
        if(!(S.base = (ElemType *)malloc(STACK_INIT_SIZE 
                                      * sizeof(ElemType))))
            exit(OVERFLOW);     // 存储分配失败
        S.top = S.base;
        S.stacksize = STACK_INIT_SIZE;
    }
    
    void DestroyStack(SqStack &S)
    {
        
        // 销毁栈S，S不再存在
        free(S.base);
        S.base = NULL;
        S.top = NULL;
        S.stacksize = 0;
    }
    
    void Push(SqStack &S, ElemType e)
    {
        
        if(S.top - S.base >= S.stacksize) {
         // 栈满，追加存储空间
            S.base = (ElemType *)realloc(S.base, (S.stacksize 
                  + STACK_INCREMENT) * sizeof(ElemType));
            if(!S.base)
                exit(OVERFLOW);           // 存储分配失败
            S.top = S.base + S.stacksize;
            S.stacksize += STACK_INCREMENT;
        }
        *(S.top)++ = e;
    }
    
    Status Pop(SqStack &S, ElemType &e)
    {
        
        // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；
        // 否则返回ERROR
        if(S.top == S.base)
            return ERROR;
        e = *--S.top;
        return OK;
    }
    
    Status GetTop(SqStack S, ElemType &e)
    {
        
        // 若栈不空，则用e返回S的栈顶元素，并返回OK；
        // 否则返回ERROR
        if(S.top > S.base) {
        
            e = *(S.top - 1);
            return OK;
        }
        else
            return ERROR;
    }
    
    Status StackEmpty(SqStack S)
    {
        
        // 若栈S为空栈，则返回TRUE，否则返回FALSE
        if(S.top == S.base)
            return TRUE;
        else
            return FALSE;
    }
    
    
    
    
    
    int main ()
    {
        
    	int n=1;
    	ElemType e,q,temp;
    	int a;
    	SqStack P;
    	InitStack(P);
    	printf("入栈输入：1 ，出栈输入：2 ，得到栈顶元素输入：3 ， 判断栈是否为空：4 ，销毁栈：5  \n");
    	while(n)
    	{
        
    		printf("输入操作："); 
    		scanf("%d",&a); 
    		switch(a)
    		{
        
    			case 1: printf("入栈操作,输入要入栈的元素："); 
    					scanf("%d",&e);
    					Push(P, e);
    					break;
    			case 2: printf("出栈操作\n"); 
    				    Pop(P, q);
    				    printf("当前出栈的元素的值为：%d\n",q);
    					break;
    			case 3: GetTop(P, temp);
    				 	printf("输出栈顶元素为 %d \n",temp);
    				 	break;
    			case 4: if(StackEmpty(P)) printf("当前栈为空\n");
    			 			else printf("当前栈不空\n"); 
    			 		break;
    			case 5: printf("---正在销毁栈---\n");
    			 		DestroyStack(P);
    			 		break;
    			 		
    		}
    			
    	}
    	
     }

判断运算符优先级函数  
//思路：  
1.先实用二维数组存储运算符的优先级  
2.使用switch语句对传入的参数进行优先级比较

//根据教科书表3.1，判断两符号的优先关系
    char Precede(char t1, char t2){
          
    	int i,j;  
        char pre[7][7]={
                   
        //运算符之间的优先级制作成一张表格  
            {
        '>','>','<','<','<','>','>'},  
            {
        '>','>','<','<','<','>','>'},  
            {
        '>','>','>','>','<','>','>'},  
            {
        '>','>','>','>','<','>','>'},  
            {
        '<','<','<','<','<','=','0'},  
            {
        '>','>','>','>','0','>','>'},  
            {
        '<','<','<','<','<','0','='}};  
        switch(t1){
          
            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(t2){
          
            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 pre[i][j];  
    }

判断字符c是否是运算符  
//思路：  
1.使用switch语句对c进行判断

//判断c是否为运算符
    Status In(OperandType c)
    {
        
    	switch(c)
    	{
        
    	case '+':
    	case '-':
    	case '*':
    	case '/':
    	case '(':
    	case ')':
    	case '=':
    		return TRUE;
    	default:
    		return FALSE;
    	}
    
    }

二元运算函数如：+ - \* /

//二元运算(a theta b)
    ElemType Operate(ElemType a, OperandType theta, ElemType b)
    {
        
    	ElemType c;
    	switch(theta)
    	{
        
    	case '+':
    		c = a + b;
    		break;
    	case '-':
    		c = a - b;
    		break;
    	case '*':
    		c = a * b;
    		break;
    	case '/':
    		c = a / b;
    		break;
    	}
    	return c;
    }

表达式求值的全部代码（可以直接运行使用）

#include <stdio.h>
    #include <stdlib.h>//函数atof()将字符串转化为一个浮点数值,atoi()将一个字符串转化为一个整数数值 
    //atol()将一个字符串转化为一个长整数
    //malloc()函数 
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1  
    #define OVERFLOW -2
    #define STACK_INIT_SIZE 100   //存储空间初始分配量
    #define STACKINCREMENT 10   //存储空间分配增量
    
    typedef char SElemType;
    typedef double ElemType;
    typedef char OperandType;   //表达式求值的运算类型
    typedef int Status;
    
    typedef struct
    {
        
    	SElemType *base;
    	SElemType *top;
    	int stacksize;
    }SqStack;
    
    
    //构造一个空栈
    Status InitStack(SqStack *S)
    {
        
    	S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    	if(!S->base)
    	{
        
    		printf("内存分配失败!\n");
    		exit(OVERFLOW);
    	}
    
    	S->top = S->base;
    	S->stacksize = STACK_INIT_SIZE;
    	return OK;
    }
    
    //若栈不为空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
    Status GetTop(SqStack *S, SElemType *e)
    {
        
    	if(S->top == S->base)
    		return ERROR;
    
    	*e = *(S->top - 1);
    	return OK;
    }
    
    //插入元素e为新的栈顶元素
    Status Push(SqStack *S, SElemType e)
    {
        
    	if(S->top - S->base >= STACK_INIT_SIZE)   //栈满， 追加存储空间
    	{
        
    		S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType));
    		if(!S->base)
    		{
        
    			printf("内存分配失败!\n");
    			exit(OVERFLOW);
    		}
    
    		S->top = S->base + S->stacksize;
    		S->stacksize += STACKINCREMENT;
    	}
    
    	*S->top++ = e;
    	
    	return OK;
    }
    
    //若栈不为空，则删除S的栈顶元素，用e返回其值，并返回Ok；否则返回ERROR
    Status Pop(SqStack *S, SElemType *e)
    {
        
    	if(S->top == S->base)
    		return ERROR;
    
    	*e =  *--S->top;
    
    	return OK;
    }
    //销毁栈S，使其不复存在
    Status StackDestroy(SqStack *S)
    {
        
    	free(S->base);
    	S->base = NULL;
    	S->top = NULL;
    	S->stacksize = 0;
    	return OK;
    }
    
    //清空栈S，保留栈底指针
    void ClearStack(SqStack *S)
    {
        
    	S->top = S->base;
    }
    
    
    
    
    
    
    
    
    typedef struct
    {
        
    	ElemType *base;
    	ElemType *top;
    	int stacksize;
    }SqStack_double;
    
    
    //构造一个空栈
    Status InitStack(SqStack_double *S)
    {
        
    	S->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    	if(!S->base)
    	{
        
    		printf("内存分配失败!\n");
    		exit(OVERFLOW);
    	}
    
    	S->top = S->base;
    	S->stacksize = STACK_INIT_SIZE;
    	return OK;
    }
    
    //若栈不为空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
    Status GetTop(SqStack_double *S, ElemType *e)
    {
        
    	if(S->top == S->base)
    		return ERROR;
    
    	*e = *(S->top - 1);
    	return OK;
    }
    
    //插入元素e为新的栈顶元素
    Status Push(SqStack_double *S, ElemType e)
    {
        
    	if(S->top - S->base >= STACK_INIT_SIZE)   //栈满， 追加存储空间
    	{
        
    		S->base = (ElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(ElemType));
    		if(!S->base)
    		{
        
    			printf("内存分配失败!\n");
    			exit(OVERFLOW);
    		}
    
    		S->top = S->base + S->stacksize;
    		S->stacksize += STACKINCREMENT;
    	}
    
    	*S->top++ = e;
    	
    	return OK;
    }
    
    //若栈不为空，则删除S的栈顶元素，用e返回其值，并返回Ok；否则返回ERROR
    Status Pop(SqStack_double *S, ElemType *e)
    {
        
    	if(S->top == S->base)
    		return ERROR;
    
    	*e =  *--S->top;
    
    	return OK;
    }
    //销毁栈S，使其不复存在
    Status StackDestroy(SqStack_double *S)
    {
        
    	free(S->base);
    	S->base = NULL;
    	S->top = NULL;
    	S->stacksize = 0;
    	return OK;
    }
    
    //清空栈S，保留栈底指针
    void ClearStack(SqStack_double *S)
    {
        
    	S->top = S->base;
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    //根据教科书表3.1，判断两符号的优先关系
    char Precede(char t1, char t2){
          
    	int i,j;  
        char pre[7][7]={
                   
        //运算符之间的优先级制作成一张表格  
            {
        '>','>','<','<','<','>','>'},  
            {
        '>','>','<','<','<','>','>'},  
            {
        '>','>','>','>','<','>','>'},  
            {
        '>','>','>','>','<','>','>'},  
            {
        '<','<','<','<','<','=','0'},  
            {
        '>','>','>','>','0','>','>'},  
            {
        '<','<','<','<','<','0','='}};  
        switch(t1){
          
            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(t2){
          
            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 pre[i][j];  
    }  
    //判断c是否为运算符
    Status In(OperandType c)
    {
        
    	switch(c)
    	{
        
    	case '+':
    	case '-':
    	case '*':
    	case '/':
    	case '(':
    	case ')':
    	case '=':
    		return TRUE;
    	default:
    		return FALSE;
    	}
    
    }
    
    //二元运算(a theta b)
    ElemType Operate(ElemType a, OperandType theta, ElemType b)
    {
        
    	ElemType c;
    	switch(theta)
    	{
        
    	case '+':
    		c = a + b;
    		break;
    	case '-':
    		c = a - b;
    		break;
    	case '*':
    		c = a * b;
    		break;
    	case '/':
    		c = a / b;
    		break;
    	}
    	return c;
    }
    
    //算术表达式求值的算符优先算法，设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合
    ElemType EvaluateExpression()
    {
        
    	SqStack OPTR;//运算符栈 
    	SqStack_double OPND;//操作数栈 
    	ElemType b,a,result;//double 类型的 
    	OperandType  x,theta;//char类型的 
    	char c;   //存放有键盘输入的字符串
    
    	char z[10];
    
    	InitStack(&OPTR);   //初始化运算符栈
    	Push(&OPTR, '=');   //=是表达式结束符
    	InitStack(&OPND);   //初始化运算数栈
    
    	c = getchar();
    	GetTop(&OPTR, &x);
    	while(c != '=' || x != '=')
    	{
        
    		if(In(c))   //是7种运算符之一
    		{
        
    			switch(Precede(x, c))
    			{
        
    			case '<':   //当前已经压栈一个运算符（x）比后一个运算符（c）低时，就将c压栈
    				Push(&OPTR, c);
    				c = getchar();
    				break;
    			case '='://消除小括号 
    				Pop(&OPTR, &x);   //脱括号并接收下一字符
    				c = getchar();
    				break;
    			case '>'://将部分表达式求值（两个操作数） 
    				Pop(&OPTR, &theta);   //退栈并将运算结果压入OPND中
    				Pop(&OPND, &b);
    				Pop(&OPND, &a);
    				Push(&OPND, Operate(a, theta, b));
    				break;
    			}
    		}
    			
    			
    			else if(c >= '0' && c <= '9'||c=='.')
    			{
        		ElemType sum=0;
    						int i=0;
    			 				//将字符串中的数字转化为数组存储 
    					while(c >= '0' && c <= '9'||c=='.') 
    					{
        
    						z[i]=c;
    						i++;
    						c = getchar();
    					}
    					z[i]='\0';
    					sum= atof(z);
    					Push(&OPND, sum);
    			}
    				
    				
    			else   //c为非法字符
    				{
        
    				printf("输入表达式有误\n");
    				exit(1);
    				}
    			GetTop(&OPTR, &x);//为了修改switch(Precede(x, c))里面的x； 
    		}
    	GetTop(&OPND, &result);//即为表达式求值得到的结果 
    	
    	return result;
    }
    
    int main()
    {
        
    	printf("请输入算术表达式，负数要用（0-正数）仅支持多位数（double）运算 例如:\n");
    	printf("\t\t\t例如 4+8-9*1+(0-3)+9*1/3=\n");
    	printf("表达式的运算结果为：%.2lf\n", EvaluateExpression());
    	return 0;
    }

程序执行的例子

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/a879f564ce8e4e2297214c2ab407de7f.png