[C++知识库]C++中缀表达式转后缀表达式 中缀转后缀c++

#include <iostream>
using namespace std;
#define MaxSize 50
typedef char ElemType;
typedef struct
{
    ElemType data[MaxSize];
    int top;
} SqStack;

//栈初始化
void initStack(SqStack &S)
{
    S.top = -1;
}
//判断栈空
bool stackEmpty(SqStack S)
{
    if(S.top == -1)
        return true;
    else
        return false;
}
//入栈
bool push(SqStack &S,ElemType x)
{
    if(S.top == MaxSize-1)
        return false;
    S.top++;
    S.data[S.top] = x;
    return true;
}
//出栈
bool pop(SqStack &S,ElemType &x)
{
    if(S.top == -1)
        return false;
    x = S.data[S.top--];
    return true;
}
//读栈顶元素
bool getTop(SqStack S,ElemType &x)
{
    if(S.top == -1)
        return false;
    x = S.data[S.top];
    return true;
}
//中缀转后缀函数
bool reversePolish(ElemType str[],int length)
{
    SqStack S;//声明符号栈
    initStack(S);//符号栈初始化
    string polish;//声明后缀表达式字符串
    int i;//i是遍历中缀表达式的下标
    for(i=0; i<length; i++)
    {
        switch(str[i])
        {
        case '(':
            push(S,str[i]);//左括号直接入栈
            break;
        case ')':
            //遇到右括号，不入栈，弹出栈中（ 上面的所有符号并加入后缀表达式，最后把左括号弹出
            ElemType topElem,x;
            getTop(S,topElem);//读取栈顶元素
            while(topElem != '(')
            {
                pop(S,x);
                polish+=x;
                if(stackEmpty(S))
                {
                    //cout<<"栈空！"<<endl;
                    break;
                }
                else
                    getTop(S,topElem);
            }

            pop(S,x);
            break;
        case '+':
        case '-':
            //先弹出比自己级别高的或者与自己同级的运算符,加入后缀表达式
            //cout<<"是+或者-，入栈"<<endl;
            if(!stackEmpty(S))//如果栈非空
            {
                ElemType topElem;
                getTop(S,topElem);//读取栈顶元素

                while(topElem == '+' || topElem == '-' || topElem == '*' || topElem == '/')
                {
                    ElemType x;
                    pop(S,x);
                    polish+=x;
                    if(stackEmpty(S))
                    {
                        //cout<<"栈空！"<<endl;
                        break;
                    }
                    else
                        getTop(S,topElem);
                }
            }
            push(S,str[i]);//弹出后自己入栈
            break;
        case '*':
        case '/':
            //先弹出比自己级别高的或者与自己同级的运算符,加入后缀表达式
            //cout<<"是*或者/，入栈"<<endl;
            if(!stackEmpty(S))//如果栈非空
            {
                ElemType topElem;
                getTop(S,topElem);//读取栈顶元素

                while(topElem == '*' || topElem == '/')
                {
                    ElemType x;
                    pop(S,x);
                    polish+=x;
                    if(stackEmpty(S))
                    {
                       // cout<<"栈空！"<<endl;
                        break;
                    }
                    else
                        getTop(S,topElem);
                }
            }
            push(S,str[i]);//弹出后自己入栈
            break;
        default:
            polish+=str[i];
        }
    }
    while(!stackEmpty(S))
    {
        ElemType x;
        pop(S,x);
        polish+=x;
    }
    cout<<"后缀表达式为："<<endl;
    cout<<polish;
    return true;
}
int main()
{
    ElemType str[MaxSize];
    int length;
    cout<<"请输入中缀字符串长度：";
    cin>>length;
    cout<<"请输入中缀表达式："<<endl;
    cin>>str;
    cout<<"您输入的中缀表达式为：";
    cout<<str<<endl;
    reversePolish(str,length);
    return 0;
}

代码有个缺点，输入的时候必须输入要测试的中缀字符串长度，我懒得改了~~其他应该还是没问题的