devbox
在线问答5
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

4.表达式求值（1）_算式求值(一)

作者：在线问答5 | 2024-07-20 20:50:21

赞

踩

算式求值(一)

4.表达式求值（1）

成绩 10 开启时间 2014年10月26日 Sunday 14:00
折扣 0.8 折扣时间 2014年11月9日 Sunday 23:55
允许迟交 否 关闭时间 2014年11月23日 Sunday 23:55

背景：

我们的教材中已经介绍了表达式求值的算法，现在我们将该算法的功能进行扩展，要求可以处理的运算符包括：+、-、*、/、%（整数取余）、^（乘方）、（、）。

要求：

采用算符优先算法，计算的中间结果只保留整数。

输入：

第一行为整数N。表示下面有N个表达式

从第二行起的后面N行为N个由整数构成的表达式

输出：

共N行，每行为相应表达式的计算结果。

如果判断出表达式有错误，则输出：error.

如果在计算过程中出现除数为0的情况，则输出：Divide 0.

特殊情况说明：

在表达式中，如果操作数出现负数（例如-8），则要特别注意。例如：
10加-8表示为：10+-8。
10减-8表示为：10--8。

  测试输入关于“测试输入”的帮助 期待的输出关于“期待的输出”的帮助 时间限制关于“时间限制”的帮助 内存限制关于“内存限制”的帮助 额外进程关于“{$a} 个额外进程”的帮助
测试用例 1 以文本方式显示
  1. 4↵
  2. 2^3↵
  3. 2^0↵
  4. 2^3^2↵
  5. 2^(3-1)^(10-8)↵
 以文本方式显示
  1. 8↵
  2. 1↵
  3. 512↵
  4. 16↵
 1秒 64M 0
测试用例 2 以文本方式显示
  1. 11↵
  2. (2+8↵
  3. 2+8)↵
  4. 8/0↵
  5. 8/(8+5-13)↵
  6. 2^(2-5)↵
  7. 10-(80-30(/3*3+4↵
  8. 10-80-30)/3*3+4↵
  9. (2+8)(3+2)↵
  10. (2)3(8)↵
  11. 30(/3+3)+4↵
  12. 10(20-8)+2↵
 以文本方式显示
  1. error.↵
  2. error.↵
  3. Divide 0.↵
  4. Divide 0.↵
  5. error.↵
  6. error.↵
  7. error.↵
  8. error.↵
  9. error.↵
  10. error.↵
  11. error.↵
 1秒 64M 0
测试用例 3 以文本方式显示
  1. 2↵
  2. 10(10)↵
  3. 14*10-(10)2↵
 以文本方式显示
  1. error.↵
  2. error.↵
 1秒 64M 0
测试用例 5 以文本方式显示
  1. 14↵
  2. 18-32↵
  3. 18/4↵
  4. 18%3↵
  5. 10+20*4↵
  6. 10-20/4↵
  7. (18-3)*3↵
  8. 10*(10)↵
  9. (10+2)/(8-10)↵
  10. (2*3)/(5*2)↵
  11. 10-(80-30)/3*3+4↵
  12. (((2+8)*2-(2+4)/2)*2-8)*2↵
  13. (((8+2)*(4/2)))↵
  14. 10/0↵
  15. (10-80*2↵
 以文本方式显示
  1. -14↵
  2. 4↵
  3. 0↵
  4. 90↵
  5. 5↵
  6. 45↵
  7. 100↵
  8. -6↵
  9. 0↵
  10. -34↵
  11. 52↵
  12. 20↵
  13. Divide 0.↵
  14. error.↵
 1秒 64M 0
#include<stdio.h>
#include<string.h>
#include<math.h>
#define CHAR 1
#define NUM 0
int check(char s)
{
	if (s == '+' || s == '-' || s == '*' || s == '/' || s == '^' || s == '%')
		return CHAR;
	else
		return NUM;
}
int cmp(char a, char b){
	if (a == b&&a == '^')
		return -1;
	if (a == b)
		return 1;
	if ((a == '*' || a == '/') && (b == '+' || b == '-'))
		return 1;
	if ((a == '+' || a == '-') && (b == '*' || b == '/'))
		return -1;
	if (a != '^'&&b == '^')
		return -1;
	if (a == '^'&&b != '^')
		return 1;
	if ((a == '+' || a == '-') && (b == '+' || b == '-'))
		return 1;
	if ((a == '*' || a == '/') && (b == '*' || b == '/'))
		return 1;
	if (a == '\0'&&check(b))
		return -1;
	if (a == '('&&check(b))
		return -1;
}
int Operator(int a, int b, char s)
{
	if (s == '+')
		return a + b;
	if (s == '-')
		return a - b;
	if (s == '*')
		return a*b;
	if (s == '/')
		return a / b;
	if (s == '%')
		return a%b;
	if (s == '^')
		return pow(a,b);
}
int main()
{
	int N;
	int i;
	char StackOperator[1000];
	int NumOperator[1000];
	char map[1000];
	int len;
	int flag_Stack;
	int flag_Num;
	int flag_temp = 1;
	int flag;
	scanf("%d", &N);
	while (N--){
		memset(StackOperator, 0, sizeof(StackOperator));
		memset(NumOperator, 0, sizeof(NumOperator));
		memset(map, 0, sizeof(map));
		StackOperator[0] = '\0';
		flag = 0;
		flag_Stack = 1;
		flag_Num = 0;
		scanf("%s", map);
		len = strlen(map);
		for (i = 0; i < len; i++){
			flag_temp = 1;
			if (i == 0 && map[i + 1] >= '0'&&map[i + 1] <= '9'&&map[0]=='-'){
				flag_temp = -1;
				i++;
				goto k;
			}
			if (i == 0 && map[i + 1] >= '0'&&map[i + 1] <= '9'&&map[0] == '+'){
				i++;
				goto k;
			}
			if (map[i] == '('){
				if (map[i - 1] == ')'){
					printf("error.\n");
					goto h;
				}
				if (map[i - 1] >= '0'&&map[i - 1] <= '9'){
					printf("error.\n");
					goto h;
				}
				if (check(map[i + 1]) && map[i + 1] != '+'&&map[i + 1] != '-'){
					printf("error.\n");
					goto h;
				}
				StackOperator[flag_Stack] = map[i];
				flag_Stack++;
				if ((map[i + 1] == '+' || map[i + 1] == '-') && map[i + 2] >= '0'&&map[i + 2] <= '9')
					i++;
			}
			else{
				if (map[i] >= '0' && map[i] <= '9'){
					if (map[i - 1] == '-'&&(check(map[i - 2])||map[i-2]=='('))
						flag_temp = -1;
				k:;
					while (1){
						if (map[i] >= '0'&&map[i] <= '9'){
							NumOperator[flag_Num] = NumOperator[flag_Num] * 10 + map[i] - '0';
							i++;
						}
						else
							break;
					}
					if (flag_temp == -1)
						NumOperator[flag_Num] *= -1;
					flag_Num++;
					i--;
				}
				else{
					if (check(map[i]) == 1){
						if (cmp(StackOperator[flag_Stack - 1], map[i]) < 0){
							StackOperator[flag_Stack] = map[i];
							flag_Stack++;
							if ((map[i + 1] == '+' || map[i + 1] == '-') && map[i + 2] >= '0'&&map[i + 2] <= '9')
								i++;
						}
						else{
							while (1){
								if (cmp(StackOperator[flag_Stack - 1], map[i])>0){
									if (NumOperator[flag_Num - 1] == 0 && StackOperator[flag_Stack - 1] == '/'){
										printf("Divide 0.\n");
										goto h;
									}
									if (NumOperator[flag_Num - 1] < 0 && StackOperator[flag_Stack - 1] == '^'){
										printf("error.\n");
										goto h;
									}
									NumOperator[flag_Num - 2] = Operator(NumOperator[flag_Num - 2], NumOperator[flag_Num - 1], StackOperator[flag_Stack - 1]);
									NumOperator[flag_Num - 1] = 0;
									flag_Num--;
									flag_Stack--;
								}
								else
									break;
							}
							StackOperator[flag_Stack] = map[i];
							flag_Stack++;
							if ((map[i + 1] == '+' || map[i + 1] == '-') && map[i + 2] >= '0'&&map[i + 2] <= '9')
								i++;
						}
					}
					else{
						if (map[i] == ')'){
							if (map[i + 1] >= '0' && map[i + 1] <= '9'){
								printf("error.\n");
								goto h;
							}
							if (map[i + 1] == '('){
								printf("error.\n");
								goto h;
							}
							while (1){
								if (StackOperator[flag_Stack - 1] != '('){
									if (NumOperator[flag_Num - 1] == 0 && StackOperator[flag_Stack - 1] == '/'){
										printf("Divide 0.\n");
										goto h;
									}
									if (NumOperator[flag_Num - 1] < 0 && StackOperator[flag_Stack - 1] == '^'){
										printf("error.\n");
										goto h;
									}
									if (StackOperator[flag_Stack - 1] == '\0'){
										printf("error.\n");
										goto h;
									}
									NumOperator[flag_Num - 2] = Operator(NumOperator[flag_Num - 2], NumOperator[flag_Num - 1], StackOperator[flag_Stack - 1]);
									NumOperator[flag_Num - 1] = 0;
									flag_Num--;
									flag_Stack--;
								}
								else{
									flag_Stack--;
									break;
								}
							}
						}
					}
				}
			}
		}
		while (1){
			if (StackOperator[flag_Stack - 1] != '\0'&&StackOperator[flag_Stack - 1] !='(' ){
				if (NumOperator[flag_Num - 1] == 0 && StackOperator[flag_Stack - 1] == '/'){
					printf("Divide 0.\n");
					goto h;
				}
				if (NumOperator[flag_Num - 1]<0 && StackOperator[flag_Stack - 1] == '^'){
					printf("error.\n");
					goto h;
				}
				NumOperator[flag_Num - 2] = Operator(NumOperator[flag_Num - 2], NumOperator[flag_Num - 1], StackOperator[flag_Stack - 1]);
				NumOperator[flag_Num-1] = 0;
				flag_Num--;
				flag_Stack--;
			}
			else{
				if (StackOperator[flag_Stack - 1] == '('){
					printf("error.\n");
					goto h;
				}
				else
					break;
			}
		}
		printf("%d\n", NumOperator[0]);
	h:;
	}
	return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/在线问答5/article/detail/858333
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号