数据结构表达式求值_1

柔光的暖阳◎ 2023-03-14 05:47 13阅读 0赞

在一个表达式中，只有“(”，“)”，“0-9”，“+”，“-”，“\*”，“/”，“^”，请求出表达式的值。(“/”用整数除法)。

输入格式:  
共1 行，为一个算式。 （算式长度<=30 其中所有数据在 0~2^31-1的范围内）。

输出格式:  
共一行，为表达式的值。

输入样例:  
在这里给出一组输入。例如：

1+(3+2)*(7^2+6*9)/(2)  
输出样例:  
在这里给出相应的输出。例如：

258

## 我的答案 ##

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<stdbool.h>
    #define maxsize 310
    
    bool isNum(char ch);
    int Calculate(int a, char str, int b);
    bool CompareChar(char a, char b);
    
    int main()
    { 
    	char ch[maxsize];
    	int num[maxsize];
    	char str[maxsize];
    	int i = 0;
    
        
    	gets(ch);
    	int topn, topc;
    	topn = 0;
    	topc = 0;
    
        
    	for (int i = 0; i < 310; i++)
    	{ 
    		num[i] = 0;
    		str[i] = '0';
    	}
    
    	while (i < strlen(ch))
    	{ 
    		if (isNum(ch[i]))
    		{ 		
    			while (isNum(ch[i]))
    			{ 
    				num[topn] = num[topn] * 10 + (ch[i++] - '0');
    			}
    			topn++;
    			continue;
    		}
    		else
    		{ 
    			if (ch[i] == '(')  str[topc++] = ch[i];
    			else if (ch[i] == ')')
    			{ 
    				while (str[topc - 1] != '(')
    				{ 
    
    					num[topn - 2] = Calculate(num[topn - 2], str[topc - 1], num[topn - 1]);
    					num[topn - 1] = 0;
    					topc--;
    					topn--;
    				}
    				topc--;
    			}
    			else
    			{ 
    				if (topc == 0) str[topc++] = ch[i];         
    				else if (CompareChar(ch[i], str[topc - 1]))        str[topc++] = ch[i];
    				
    				else
    				{ 
    		
    					while (!CompareChar(ch[i], str[topc - 1]))
    					{ 
    						if (str[topc - 1] == '(')	break;
    
    						num[topn - 2] = Calculate(num[topn - 2], str[topc - 1], num[topn - 1]);
    						num[topn - 1] = 0;
    						topc--;
    						topn--;
    
    						if (topc == 0)	break;
    					}
    					str[topc++] = ch[i];
    				}
    			}
    		}
    		i++;
    	}
    
    	while (topn != 1 && topc > 0) 
    	{ 
    		num[topn - 2] = Calculate(num[topn - 2], str[topc - 1], num[topn - 1]);
    		topn--;
    		topc--;
    	}
    	printf("%d", num[0]);
    }
    
    bool isNum(char ch)
    { 
    	if (ch <= '9' && ch >= '0')  return true;
    	else return false;
    }
    
    int Calculate(int a, char str, int b)
    { 
    	if (str == '*')       return a * b;
    	else if (str == '/')  return a / b;
    	else if (str == '-')  return a - b;
    	else if (str == '+')  return a + b;
    	else                  return pow(a, b);
    }
    
    bool CompareChar(char a, char b)
    { 
    	int x = 0; 
    	int y = 0; 
    
    	if (a == '+' || a == '-')       x = 1;
    	else if (a == '*' || a == '/')  x = 2;
    	else if (a == '^')              x = 3;
    	else if (a == '(')              x = 4;
    	if (b == '+' || b == '-')       y = 1;
    	else if (b == '*' || b == '/')  y = 2;
    	else if (b == '^')              y = 3;
    	else if (b == '(')              y = 4;
    
    	if (x > y)                      return true;
    	else                            return false;
    }