【数据结构】利用栈求解表达式

雨点打透心脏的1/2处 2022-08-25 08:52 139阅读 0赞

表达式求值问题，其中运算符号只包含 加减乘除 取整数 详细请参见代码：

#include <stdio.h>
    
    #define MAX_SIZE 100
    
    typedef struct 
    {
    	int top;
    	char data[MAX_SIZE];
    }NumStack;
    
    typedef struct 
    {
    	int top;
    	char opera[MAX_SIZE];
    }OperaStack;
    
    const char perior[5][5] = 
    {
    	'>','>','<','<','>',
    	'>','>','<','<','>',
    	'>','>','>','>','>',
    	'>','>','>','>','>',
    	'<','<','<','<','<',
    };
    
    void NumPush(NumStack* L,int elem);
    void OperaPush(OperaStack* L, char elem);
    int NumPop(NumStack* L);
    char OperaPop(OperaStack* L);
    char comp_perior(char a,char b);
    int compute(int a,int b,char c);
    int pe2int(char a);
    
    void main()
    {
    	int i = 0;
    	int j = 0;
    	int num = 0;
    	char expression[20] = "14+13-2*9+24/3=";
    
    	NumStack Num_stack = {0,};
    	OperaStack Opera_stack = {0,};
    
    	while (expression[i] != '\0')
    	{
    		switch (expression[i])
    		{
    		case '0':
    		case '1':
    		case '2':
    		case '3':
    		case '4':
    		case '5':
    		case '6':
    		case '7':
    		case '8':
    		case '9':
    			num = 10*num + (expression[i]-'0');
    			break;
    		case '=':
    			if (expression[i+1] != '\0')
    				return;
    		case '+':
    		case '-':
    		case '*':
    		case '/':
    			NumPush(&Num_stack,num);
    
    			if (Opera_stack.top == 0 || comp_perior(Opera_stack.opera[Opera_stack.top-1],expression[i]) == '<')
    				OperaPush(&Opera_stack,expression[i]); // 栈空时直接入栈
    			else 
    			{
    				do
    				{
    					int temp = compute(NumPop(&Num_stack),NumPop(&Num_stack),OperaPop(&Opera_stack));
    					NumPush(&Num_stack,temp);
    				}while (comp_perior(Opera_stack.opera[Opera_stack.top-1],expression[i]) == '>');
    
    				OperaPush(&Opera_stack,expression[i]);
    			}
    
    			num = 0;
    			break;
    		}
    		i++;
    	}
    
    	printf("计算的结果 = %d\n",Num_stack.data[Num_stack.top-1]);
    }
    
    void NumPush(NumStack* L,int elem)
    {
    	if (L->top+1 < MAX_SIZE)
    		L->data[L->top++] = elem;
    }
    
    
    void OperaPush(OperaStack* L, char elem)
    {
    	if ((L->top+1) < MAX_SIZE)
    		L->opera[L->top++] = elem;
    }
    
    
    int NumPop(NumStack* L)
    {
    	if (L->top == 0)
    		return -1;
    
    	return (L->data[--L->top]);
    }
    
    
    char OperaPop(OperaStack* L)
    {
    	if (L->top == 0)
    		return -1;
    
    	return (L->opera[--L->top]);
    }
    
    char comp_perior(char a,char b)
    {
    	return perior[pe2int(a)][pe2int(b)];
    }
    
    int pe2int(char a)
    {
    	switch (a)
    	{
    	case '+':
    		return 0;
    	case '-':
    		return 1;
    	case '*':
    		return 2;
    	case '/':
    		return 3;
    	case '=':
    		return 4;
    	default:
    		return -1;
    	}
    }
    
    int compute(int a,int b,char c)
    {
    	switch(c)
    	{
    	case '+':
    		return a+b;
    	case '-':
    		return a-b;
    	case '*':
    		return a*b;
    	case '/':
    		return a/b;
    	}
    }