NYOJ-467 中缀式变后缀式

「爱情、让人受尽委屈。」 2022-08-25 05:28 150阅读 0赞

## 中缀式变后缀式 ##

时间限制： 1000 ms |  内存限制： 65535 KB

难度： 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 / =

做题时在输出空格花了些时间

\#define TRUE 1  
\#define FALSE 0  
\#define STACK\_INIT\_SIZE 10002

\#include "iostream"  
\#include "cstdlib"  
\#include "cstdio"  
\#include "cstring"

using namespace std;

typedef int Status; //Status 相当于 int  
typedef struct Stack1 //运算符栈  
\{  
char \* base;  
char \* top;  
\}SqStack1;

//运算符栈操作  
void  InitStack1(SqStack1 &S) //创建一个空栈  
\{

S.base = (char \*)malloc(sizeof(char) \* STACK\_INIT\_SIZE);  
S.top = S.base;  
\}  
Status Stack1Empty(SqStack1 S)//判断是否为空  
\{  
if(S.top == S.base) return TRUE;  
else return FALSE;  
\}  
void Push1(SqStack1 &S,char e )//插入元素e为新的栈顶元素  
\{  
\* S.top++ = e;  
\}  
void Pop1(SqStack1 &S,char &e)//出栈  
\{  
e = \* --S.top ;  
\}  
char GetTop1(SqStack1 S)  
\{  
return \*(S.top-1);  
\}  
void TraverseStack1(SqStack1 S)//输出当前顺序表  
\{  
char \* p = S.base;  
cout<<"运算栈中的元素为：";  
while( p != S.top  )  
\{  
cout<<\*p<<" ";  
p++;  
\}  
cout<<endl;  
\}

Status In(char ch)//判断ch是否为运算符  
\{  
if(ch == '+' || ch == '('|| ch == '-' || ch == '\*' || ch == '/' || ch == ')'  || ch == '=') return TRUE;  
else return FALSE;  
\}

void In\_to\_Ne(char s\[1002\], char p\[1002\],int &l)  
\{  
char c,ch;  
Stack1 S; InitStack1(S);  
int i,k, len;  
k = 0;  
len = strlen(s);  
for(i = 0; i< len ; ++i)  
\{  
c =s\[i\];  
// printf("c = %c\\n",c);  
if( !In(c) )  
\{  
while(!In(c) )\{  
p\[k++\] = c;  
c = s\[++i\];  
\}  
p\[k++\] = ' ';  
\}//操作数  
if( Stack1Empty(S) ) Push1(S,c);  
else if( c == '(' )  Push1(S,c);  
else if(c == ')'  )  
\{  
while( GetTop1(S)!= '(')  
\{  
Pop1(S,ch);p\[k++\] = ch; p\[k++\] =' ';  
\}  
Pop1(S,ch); //将（出栈  
\} //将栈顶元素弹出并放到p  
else if( (c == '+' || c=='-' )&&(GetTop1(S)=='(' ) ) Push1(S,c);  
else if( (c == '+' || c=='-' )&&(GetTop1(S) =='+' ||GetTop1(S)=='-'||GetTop1(S)=='\*' ||GetTop1(S)=='/' ) ) \{  Pop1(S,ch);  p\[k++\] = ch; p\[k++\] =' ';  i = i-1;  \} //将栈顶元素弹出并放到p  
else if( (c == '\*' || c=='/' )&&(GetTop1(S) =='+' ||GetTop1(S)=='-'|| GetTop1(S)=='(' ) ) Push1(S,c);  
else if( (c == '\*' || c=='/' )&&(GetTop1(S) =='\*' ||GetTop1(S)=='/') ) \{  Pop1(S,ch);  p\[k++\] = ch; p\[k++\] =' '; i = i-1;  \} //将栈顶元素弹出并放到p  
// TraverseStack1(S);  
\}

while(!Stack1Empty(S) )  
\{  
Pop1(S,ch);  p\[k++\] = ch; p\[k++\] =' ';  
\}  
l = k;  
return ;  
\}  
  
int main()  
\{  
char s\[1002\], p\[1002\];  
int n,i,len;  
scanf("%d",&n);  
while(n--)  
\{  
scanf("%s",s);  
In\_to\_Ne( s, p,len);  
for(i =0; i  
printf("%c",p\[i\]);  
printf("=\\n");  
\}  
return 0;  
\}