游客 注册 | 登录
中文 | En

2388 - 后缀表达式

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

       为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为后缀{运算符在后，如X/Y写为XY/表达式。在这样的表示中可以不用括号即可确定求值的顺序，如：(P+Q)*(R－S) → PQ+RS－*。后缀表达式的处理过程如下：扫描后缀表达式，凡遇操作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描，直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。

      输入一个中缀表达式，编程输出其后缀表达式，要求输出的后缀表达式的运算次序与输入的中缀表达式的运算次序相一致。为简单起见，假设输入的中缀表达式由＋（加）、－（减）、×（乘）、／（除）四个运算符号以及左右圆括号和英文字母组成，其中算术运算符遵守先乘除后加减的运算规则。假设输入的中缀表达式长度不超过200个字符，且都是正确的，即没有语法错误，并且凡出现括号其内部一定有表达式，即内部至少有一个运算符号。

题目输入

只有一行，为中缀表达式

题目输出

只有一行，为转换后的后缀表达式

输入/输出样例

输入格式

X+A*(Y-B)-Z/F

输出格式

XAYB-*+ZF/-

C语言解答

#include<stdio.h>
#include<stdlib.h>

typedef char ElemType;
typedef enum {TRUE,FALSE,OVERFLOW} Status;
#define MAXSIZE 200	//定义栈的最大容量
typedef struct
{
	ElemType elem[MAXSIZE];	//存放栈中元素的一维数组空间
	int top;			//栈顶指针变量
}SeqStack;

void InitStack (SeqStack *S)
{	//构造一个空栈S
	S -> top = 0;
}

Status StackEmpty (SeqStack *S)
{	//判断S是否为空栈，为空时返回TRUE，否则返回FALSE
	return (S->top == 0 ? TRUE : FALSE);
}

Status Push (SeqStack *S, ElemType e)
{	//将数据元素e压入栈顶
	if (S -> top == MAXSIZE)  return FALSE;//栈已满，进栈失败
	S -> elem[S -> top] = e;			//将e插入栈顶
	S -> top ++;				//修改栈顶指针
	return TRUE;
}

Status GetTop (SeqStack *S, ElemType *e)
{	//若栈不空，则用e返回栈顶元素
	if (S->top == 0)  return FALSE;
	*e = S->elem[S->top - 1];		//保存栈顶元素
	return TRUE;
}

Status Pop (SeqStack *S, ElemType *e)
{	//若栈不空，将栈顶元素弹出，并用e返回其值
	if (S -> top == 0)  
		return FALSE;
	else
	{
		S -> top --;			//修改栈顶指针
		*e = S -> elem[S -> top];	//保存栈顶元素
		return TRUE; 
	}
}

//全局变量 
SeqStack S;
char C[MAXSIZE];

int main()
{
	int i;
	ElemType e;
	scanf("%s",C);
	for(i=0;C[i]!='\0';i++)
	{
		if((C[i]>='A' && C[i]<='Z') || (C[i]>='a' && C[i]<='z'))
			printf("%c",C[i]);
		else if(C[i]=='+' || C[i]=='-')
		{
			while(GetTop(&S,&e)==TRUE)
			{
				if(e=='+' || e=='-' || e=='*' || e=='/')
				{
					Pop(&S,&e);
					printf("%c",e);
				}
				else
					break;
			}
			Push(&S,C[i]);
		}
		else if(C[i]=='*' || C[i]=='/')
		{
			while(GetTop(&S,&e)==TRUE)
			{
				if(e=='*' || e=='/')
				{
					Pop(&S,&e);
					printf("%c",e);
				}
				else
					break;
			}
			Push(&S,C[i]);
		}
		else if(C[i]=='(')
		{
			Push(&S,C[i]);
		}
		else
		{
			while(GetTop(&S,&e)==TRUE)
			{
				if(e=='(')
				{
					Pop(&S,&e);
					break;
				}
				else
				{
					Pop(&S,&e);
					printf("%c",e);
				}
			}
		}
	}	
	while(Pop(&S,&e)==TRUE)
	{
		printf("%c",e);
	}
	printf("\n");
	return 0;
}

C++解答

#include<iostream>
#include<cstring>
#include<stack>
#include<cstdio>
using namespace std;
string s;
stack<char> a;
bool isoperator(char);
int getpre(char,bool);
void work();
int main()
{
	//freopen("hz.in","r",stdin);
	//freopen("hz.out","w",stdout);
	cin>>s;	
	work();
	return 0;
}
void work()
{
	int i;
	for(i=0;i<s.size();++i)
	{
		if(!isoperator(s[i]))
		{
			cout<<s[i];
			continue;
		}
		else
		{
			if(a.empty())
			{
				a.push(s[i]);
				continue;
			}
			else
			{
				if(s[i]==')')
				{				
					while(a.top()!='('&& !a.empty())
					{
						cout<<a.top();
						a.pop();					
					}
					a.pop();
					continue;				
				}					
				while(!a.empty()&&getpre(s[i],false)<=getpre(a.top(),true))
				{
					cout<<a.top();
					a.pop();
				}
				a.push(s[i]);
			}						
		}		
	}
	while(!a.empty())
	{
		cout<<a.top();
		a.pop();
	}
}
bool isoperator(char ch)
{
	if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch==')'||ch=='(')return true;
	else return false;
}
int getpre(char ch,bool flag)
{
	if(ch=='+'||ch=='-') return 1;
	if(ch=='*'||ch=='/') return 2;
	if(ch=='('&&flag) return 0;
	if(ch=='('&&!flag) return 3;
}
请先登陆