2kb

用户名：yifang

访问量：11726

签　名：

等　　级
排　　名	2130
经　　验	2384
参赛次数	2
文章发表	21
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

迷宫问题-题解(C++代码)
浏览：308

数据结构-有序线性表的有序合并-题解(C语言代码)
浏览：711

数据结构-Big Bang-题解(C语言代码)
浏览：1078

你可能喜欢

C语言程序设计教程（第三版）课后习题3.7 （Java代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

数据结构-表达式求值-题解(C语言代码)

　　作者: 2kb　　　　发表时间：2019-09-01 12:55:40 浏览：1926　|　评论：0　

原题链接：数据结构-表达式求值

解题思路：使用一个操作数栈和一个操作符栈，并为每一个操作符排一个优先级。在读取输入时，判断是数还是符，如果是符号，则获取操作符栈顶元素值，也就是操作符对应的数值，判断当前符号优先级是否大于栈顶元素，大于则将当前符号push,否则，对操作符栈使出栈操作，对操作数栈使两次出栈操作，将计算结果push操作符栈，如此往复，直到当前符号优先级大于操作符栈的栈顶元素值。
	需要注意对括号“（）”的处理，思路是这样的：
	首先，如果当前符号是“（”，则push操作符栈。
	然后，对其他操作符的处理额外增加判断当前操作符栈栈顶元素值是否是“（”的代码，如果是，则不管当前操作符的优先级，直接push操作符栈。不是的话，正常处理操作符的优先级。
	当当前符号是“）”时，对操作符栈使出栈操作,对操作数栈使两次出栈操作，
	计算结果，然后push操作数栈。如此往复，直到当前操作符是“（”，括号处理完毕。
### 	解题思路仅供参考。
	
	#include <stdio.h>
    #include <string.h>
    #include <malloc.h>
    
    typedef struct _node
    {
    	int data; 
    	struct _node* next;
    }Node;
    
    
    
    void push(Node** root, int data)
    {
    	Node* no = (Node*)malloc(sizeof(Node));
    	no->data = data;
    	no->next = *root;// 
    	
    	*root = no;
    }
    int top(Node** root)
    {
    	if(*root == NULL)
    		return 0;//栈为空
    	return (*root)->data; 
    }
    int pop(Node** root)
    {
    	if(*root == NULL)
    		return 0;	//栈为空
    	Node* temp = (*root)->next;
    	
    	free(*root);//释放栈顶指针内存 
    	*root = temp;//将栈顶指针下移 
    	return 1;
    }
    int calculat2(int le, int op1, int op2)
    {
    	int sum = 0;
    	switch(le)
    	{
    		case 1://+ 
    			sum = op1 + op2;
    			break;
    		case 2:// - 
    			sum = op2 - op1;
    			break;
    		case 3:// * 
    			if(op2 != 0 && op1 != 0)
    			{
    				sum = op1 * op2;
    			}else
    				sum = 0; 
    			break;
    		case 4:// / 
    			if(op2 != 0 && op1 != 0)
    			{
    				sum = op2 / op1;
    			}else
    				sum = 0;
    			break;
    	}
    	return sum;
    }
    int calculat(char a[])
    {
    	Node* oper = NULL;//操作数栈 
    	Node* oper2 = NULL;//运算符栈
    	int i = 0; 
    	//int isbracket = 0;//是否有括号 
    	//#:0 +:1 -:2 *:3 /:4
    	while(1)
    	{
    		
    		if(a[i] == '+')
    		{
    			while(1)
    			{
    				int level = top(&oper2);
    				if(level == 5 || 1 > level) 
    				{
    					push(&oper2,1);
    					break;
    				}else
    				{
    					pop(&oper2);
    					int op1 = top(&oper);
    					pop(&oper);
    					int op2 = top(&oper);
    					pop(&oper);	
    					push(&oper,calculat2(level, op1, op2));
    				}
    			}
    			i++;
    		}else if(a[i] == '-')
    		{
    			while(1)
    			{
    				int level = top(&oper2);
    				if(level == 5 || 1 > level) 
    				{
    					push(&oper2,2);
    					break;
    				}else
    				{
    					pop(&oper2);
    					int op1 = top(&oper);
    					pop(&oper);
    					int op2 = top(&oper);
    					pop(&oper);	
    					push(&oper,calculat2(level, op1, op2));
    				}
    			}
    			i++;
    		}else if(a[i] == '*')
    		{
    			while(1)
    			{
    				int level = top(&oper2);
    				if(level == 5 || 3 > level) 
    				{
    					push(&oper2,3);
    					break;
    				}else
    				{
    					pop(&oper2);
    					int op1 = top(&oper);
    					pop(&oper);
    					int op2 = top(&oper);
    					pop(&oper);
    					push(&oper,calculat2(level, op1, op2));
    				}
    			}
    			i++;
    		}else if(a[i] == '/')
    		{
    			while(1)
    			{
    				int level = top(&oper2);
    				if(level == 5 || 3 > level) 
    				{
    					push(&oper2,4);
    					break;
    				}else
    				{
    					pop(&oper2);
    					int op1 = top(&oper);
    					pop(&oper);
    					int op2 = top(&oper);
    					pop(&oper);	
    					push(&oper,calculat2(level, op1, op2));
    				}
    			}
    			i++;
    		}else if(a[i] == '(')//做特殊处理 
    		{
    			push(&oper2,5);
    			i++;
    		}
    		else if(a[i] == ')')//做特殊处理 
    		{
    			while(1)
    			{
    				
    				int level = top(&oper2);
    				if(level == 5)
    				{
    					pop(&oper2);
    					break;
    				}
    				pop(&oper2);
    				int op1 = top(&oper);
    				pop(&oper);
    				int op2 = top(&oper);
    				pop(&oper);
    				push(&oper, calculat2(level, op1, op2));
    			}
    			i++;
    		}else if(a[i] == '#')
    		{
    			while(1)
    			{
    				int level = top(&oper2);
    				if(0 == level) 
    				{
    					break;
    				}else
    				{
    					pop(&oper2);
    					int op1 = top(&oper);
    					pop(&oper);
    					int op2 = top(&oper);
    					pop(&oper);	
    					push(&oper,calculat2(level, op1, op2));
    				}
    			}
    			break;
    		}else if(a[i] >= '0' && a[i] <= '9')
    		{
    			int num = 0;
    			
    			while(a[i] >= '0' && a[i] <= '9')
    			{
    				num = num * 10 + (a[i] - '0');//转为整数
    				++i; 
    			}
    			push(&oper,num);
    		}
    	}
    	return top(&oper);
    }
    int main()
    {
    	char A[50];
    	int i = 0;
    	//printf("%d",'a');
    	
    	while(scanf("%c",&A[i]) != EOF)
    	{
    		if(A[i] == '#')
    		{
    			printf("%d\n",calculat(A));
    			
    			i = 0;
    			continue;
    		}else if(A[i] == '\n')
    		{
    			continue;
    		}
    		++i;
    	}
    	
    	return 0;
    }

0.0分

11 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

2kb

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题3.7 （Java代码）

The 3n + 1 problem （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

点我有惊喜！你懂得！

数据结构-表达式求值-题解(C语言代码)

评论区

精彩推荐

输出九九乘法表（C语言代码）

汽水瓶（C语言代码）

c primer plus 第十二章 12.1小节

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

简单的a+b （C语言代码）

【偶数求和】（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

【蟠桃记】（C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

【计算球体积】（C语言代码）

2kb

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题3.7 （Java代码）

The 3n + 1 problem （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

点我有惊喜！你懂得！

数据结构-表达式求值-题解(C语言代码)

评论区

精彩推荐

输出九九乘法表 （C语言代码）

汽水瓶 （C语言代码）

c primer plus 第十二章 12.1小节

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

简单的a+b （C语言代码）

【偶数求和】 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

【蟠桃记】 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

【计算球体积】 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

　　评论区

输出九九乘法表（C语言代码）

汽水瓶（C语言代码）

【偶数求和】（C语言代码）

【蟠桃记】（C语言代码）

【计算球体积】（C语言代码）