加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 综合聚焦 > 服务器 > 安全 > 正文

nyoj.467 中缀式变后缀式【数据结构】 2015/03/11

发布时间:2020-12-15 06:01:52 所属栏目:安全 来源:网络整理
导读:中缀式变后缀式 时间限制: 1000 ms | 内存限制: 65535 KB 难度: 3 描述 人们的日常习惯是把算术表达式写成中缀式,但对于机器来说更“习惯于”后缀式,关于算术表达式的中缀式和后缀式的论述一般的数据结构书都有相关内容可供参看,这里不再赘述,现在你

中缀式变后缀式

时间限制: 1000ms | 内存限制: 65535KB
难度: 3
描述
人们的日常习惯是把算术表达式写成中缀式,但对于机器来说更“习惯于”后缀式,关于算术表达式的中缀式和后缀式的论述一般的数据结构书都有相关内容可供参看,这里不再赘述,现在你的任务是将中缀式变为后缀式。
输入
第一行输入一个整数n,共有n组测试数据(n<10)。
每组测试数据只有一行,是一个长度不超过1000的字符串,表示这个运算式的中缀式,每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。
数据保证除数不会为0
输出
每组都输出该组中缀式相应的后缀式,要求相邻的操作数操作符用空格隔开。
样例输入
2
1.000+2/4=
((1+2)*5+1)/4=
样例输出
1.000 2 4 / + =
1 2 + 5 * 1 + 4 / =
 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
/*
利用栈和队列操作,栈储存运算符,队列可以得到最后的后缀表达式
*/
int compare( char ch ){
	if( ch == '(' ) 
		return 0;
	if( ch == '+' )
		return 1;
	if( ch == '-' )
		return 1;
	if( ch == '*' )
		return 2;
	if( ch == '/' )
		return 2;
}
int main(){
	int n,i,j,l,opr_i,opr_j,isnum,exp_i,res_i;
	char s[1010];
	char opr[1010][10];
	char exp[1010][2];
	char temp[10];
	scanf("%d",&n);
	while(n--){
		scanf("%s",s);
		memset(opr,'',sizeof(opr));
		memset(exp,sizeof(exp));
		i = opr_i = opr_j = exp_i = res_i = 0;
		while( s[i] != '' ){
			j = isnum = 0;
			while( (s[i]>='0' && s[i]<='9') || s[i]=='.' ){
				isnum = 1;
				temp[j++] = s[i++];
			}
			if( isnum ){
				temp[j] = '';
				strcpy( opr[opr_i++],temp );
			}
			else{
				temp[0] = s[i++];
				temp[1] = '';
				switch( temp[0] ){
					case '(':strcpy( exp[exp_i++],temp );break;
					case '+':
					case '-':
					case '*':
					case '/':if( exp_i != 0 )
								while( compare(temp[0]) <= compare(exp[exp_i-1][0]) ){
									strcpy( opr[opr_i++],exp[--exp_i] );
									if( exp_i == 0 ) break;
								}
								strcpy( exp[exp_i++],temp );break;
					case ')':while( exp[exp_i-1][0] != '(' ){
								strcpy( opr[opr_i++],exp[--exp_i] );
							}
							--exp_i;break;
				}
			}
		}
		while( exp_i >= 0 )
			strcpy( opr[opr_i++],exp[--exp_i] );
		for( ; opr_j < opr_i ; ++opr_j ){
			res_i = 0;
			while( opr[opr_j][res_i] != '' ){
				printf("%c",opr[opr_j][res_i++]);
			}
			j++;
			printf(" ");
		}
		printf("=n");
	}
	return 0;
}        

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读