本文作者:佚名

HDU1237 简单的计算器 【堆】+【逆波兰式】

佚名 2019-04-03 ???
摘要:简单的计算器Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 11955Acc


简单的计算器

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 11955 Accepted Submission(s): 3896

Problem Description读入一个仅仅包括 +, -, *, / 的非负整数计算表达式,计算该表达式的值。

Input測试输入包括若干測试用例,每一个測试用例占一行,每行不超过200个字符,整数和运算符之间用一个空格分隔。没有非法表达式。当一行中仅仅有0时输入结束,对应的结果不要输出。



Output对每一个測试用例输出1行,即该表达式的值,精确到小数点后2位。

Sample Input

1 + 24 + 2 * 5 - 7 / 110

Sample Output
3.0013.36

关键地方是在把中缀式转换成后缀式时要保持符号栈从顶開始严格递减。否则先出栈,再进栈。

#include #include char str[202], buf[202], sign[202] //buf存储逆波兰式double stack[202], aint len, n, id, id2, id3, id4double perform(double x, double y, char ch){	if(ch == '*') return x * y	if(ch == '/') return x / y	if(ch == '+') return x + y	return x - y}void check(char ch){	buf[id2++] = ' '	if(ch == '*' || ch == '/'){			while(id3 && (sign[id3-1] == '*' || sign[id3-1] == '/')) 			buf[id2++] = sign[--id3]		sign[id3++] = ch		return	}	while(id3) buf[id2++] = sign[--id3]	sign[id3++] = ch}int main(){		while(gets(str)){		len = strlen(str)		if(len == 1 && str[0] == Ɔ') break		id = id2 = id3 = id4 = 0		for(int i = 0 i < len ++i){			if(str[i] == ' ') continue			if(str[i] >= Ɔ' && str[i] <= Ə'){				buf[id2++] = str[i]			}else check(str[i])		}		while(id3) buf[id2++] = sign[--id3]		//for(int i = 0 i < id2 ++i) putchar(buf[i])	 	for(int i = 0 i < id2 ++i){			if(buf[i] == ' ') continue			if(buf[i] >= Ɔ' && buf[i] <= Ə'){				sscanf(buf + i, %lf%n, &stack[id4++], &n)				i += n - 1			}else stack[id4-2] = perform(stack[id4-2], stack[id4-1], buf[i]), --id4					}				printf(%.2lf\n, stack[0])	}	return 0}

2014-11-3 21:55:30更新

#include #include #define maxn 1000char buf[maxn], out[maxn], stack[maxn]int id, id1, idadouble A[maxn]int level(char ch) {	if(ch == '+' || ch == '-') return 1	return 2}void check(char ch) {	while(id1 && level(stack[id1-1]) >= level(ch)) {		out[id++] = stack[--id1]	}	stack[id1++] = ch}double cal(double a, double b, char ch) {	if(ch == '-') return a - b	if(ch == '+') return a + b	if(ch == '*') return a * b	return a / b}int main() {	int i, n	bool sign	double a	while(gets(buf)) {		if(strlen(buf) == 1 && buf[0] == Ɔ')			break		id = id1 = 0 sign = 0		for(i = 0 buf[i] ++i) {			if(buf[i] == ' ') continue			if(buf[i] >= Ɔ' && buf[i] <= Ə' || buf[i] == '.') {				if(sign) {					out[id++] = ' '					sign = 0				}				out[id++] = buf[i]			}			else sign = 1, check(buf[i])		}		while(id1) {			out[id++] = stack[--id1]		}		for(i = ida = 0 i < id ++i) {			if(out[i] == ' ') continue			if(out[i] >= Ɔ' && out[i] <= Ə' || out[i] == '.') {				sscanf(out + i, %lf%n, &a, &n)				A[ida++] = a i += n - 1			} else A[ida-2] = cal(A[ida-2], A[ida-1], out[i]), --ida		}		printf(%.2lf\n, A[0])	}	return 0}


版权声明:本文博主原创文章,博客,未经同意不得转载。

未经允许不得转载:

作者:佚名,标题:HDU1237 简单的计算器 【堆】+【逆波兰式】,原文地址:https://www.vfjianzhan.com/php/zifuchuan/77396.html发布于2019-04-03
转载或复制请以超链接形式并注明出处唯福建站

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏