HDU 1237単純計算機【スタック】+【逆ポーランド式】

たんじゅんけいさんき
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
テスト入力には、各テスト・インスタンスが1行を占め、各行が200文字を超えず、整数と演算子の間にスペースで区切られたいくつかのテスト・インスタンスが含まれます.不正な式はありません.1行に0しかない場合は入力が終了し、対応する結果は出力されません.
 
Output
各テストケースに1行、すなわち式の値を小数点以下2桁まで出力します.
 
Sample Input

   
   
   
   

    
    
    
    1 + 2
4 + 2 * 5 - 7 / 11
0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    3.00
13.36
   
   
   
   

重要なのは、接尾辞式を接尾辞式に変換するときに、シンボルスタックをトップから厳格に減算しないと、先にスタックを出てからスタックに入ることです.

#include <stdio.h>
#include <string.h>
char str[202], buf[202], sign[202]; //buf      
double stack[202], a;
int len, n, id, id2, id3, id4;

double 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] == '0') break;
		id = id2 = id3 = id4 = 0;
		for(int i = 0; i < len; ++i){
			if(str[i] == ' ') continue;
			if(str[i] >= '0' && str[i] <= '9'){
				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] >= '0' && buf[i] <= '9'){
				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
", stack[0]);
	}
	return 0;
}

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

#include <stdio.h>
#include <string.h>

#define maxn 1000

char buf[maxn], out[maxn], stack[maxn];
int id, id1, ida;
double 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] == '0')
			break;
		id = id1 = 0; sign = 0;
		for(i = 0; buf[i]; ++i) {
			if(buf[i] == ' ') continue;
			if(buf[i] >= '0' && buf[i] <= '9' || 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] >= '0' && out[i] <= '9' || 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
", A[0]);
	}
	return 0;
}