Problem1820--【栈和队列】3-12 中缀表达式转化为后缀表达式

1820: 【栈和队列】3-12 中缀表达式转化为后缀表达式

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

输入一个中缀算术表达式,将其转换为后缀表达式。运算符包括+、-、*、/、(、)、=,参加运算的为小于10的自然数。(只考虑二元运算即可)

Input

多组数据,每组数据一行,对应一个算术表达式,每个表达式均以“=”结尾。当表达式只有一个“=”时,输入结束。

Output

对于每组数据输出一行,为表达式的后缀式。

Sample Input Copy

9+(3-1)*3+1/2=
1+2=
=

Sample Output Copy

931-3*+12/+
12+

HINT

#include<iostream>
using namespace std;
#define  MAXSIZE  100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define Status int
typedef struct
{
    char *base;
    char *top;
    int stacksize;
}SqStack;
Status InitStack(SqStack &S)
{//初始化栈
    S.base=new char[MAXSIZE];
    if(!S.base) return OVERFLOW;
    S.top=S.base;
    S.stacksize=MAXSIZE;
    return OK;
}
Status Push(SqStack &S, char e)
{//入栈
    if(S.top-S.base==S.stacksize)  //栈满
        return ERROR;
    *S.top=e;
    S.top++;
    return OK;
}
Status Pop(SqStack &S)
{//出栈
    if(S.top==S.base)   //栈空
        return ERROR;
    S.top--;
    return OK;
}
char GetTop(SqStack S)
{//取栈顶元素
    if(S.top!=S.base)
        return *(S.top-1);
    return ERROR;
}
char Precede(char a,char b)
{//比较符号优先级
    if((a=='('&&b==')')||(a=='='&&b=='='))
        return '=';
    else if(a=='='||a=='('||b=='('||((a=='+'||a=='-')&&(b=='*'||b=='/')))
        return '<';
    else
        return '>';
}
void InfixToSuffix(SqStack op,char s[])
{//将中缀表达式转化为后缀表达式并输出
    /**************begin************/
   

   
    /**************end************/
}
int main()
{
    SqStack op;
    InitStack(op);      //初始化字符栈op
    Push(op,'=');       //先在栈底放入'='便于以后比较符号优先级  
    char s[100];
    while(cin>>s)
    {
        if(s[0]=='=')
            break;      //当表达式只有一个“=”时,输入结束
        else
            InfixToSuffix(op,s);    //将中缀表达式转化为后缀表达式并输出
    }
    return 0;
}

Source/Category