C++实现中缀表达式转后缀表达式

无聊瞎翻，翻到以前写一半，没完成的代码，突然来了兴趣，填下坑。

 *      用栈保存运算符
 *      前缀：Prefix Notation(Polish notation)
 *      中缀：Infix Notation
 *      后缀：Postfix Notation(Reverse Polish notation)
 *      操作数：A-Z, a-z, 0-9
 *      运算符：+, -, *, /, (, )
 *      Infix:输入字符串
 *      StackOp:运算符栈
 *      Postfix:输出字符串

// 中缀转后缀
string InfixConvertToPostFix(string Infix)
{
    string Postfix = ""; // 输出串
    // 初始化操作符栈
    SqStack StackOp;
    InitStack(StackOp);
    // 遍历Infix
    // 从左到右扫描InifxS
    for (int i = 0; i < Infix.length(); i++)
    {
        string OpSign = JudgeOperation(Infix[i]);  // 判断当前扫描到的字符是哪一种类型
    // -------------------------------------------
        // 错误直接退出循环
        if (OpSign == "InvalidInput")
        {
            cout << "表达式有误！" << endl;
            break;
        }
    // -------------------------------------------
        // 遇到操作数，加入表达式Postfix内
        if (OpSign == "Operand")
            Postfix.append(Infix,i, 1); //把Infix，i位置起1个元素append到Postfix中
    // -------------------------------------------
        // 遇到运算符
        if (OpSign == "Operator")
        {
            // 栈空，不管什么运算符，直接入栈
            if (StackEmpty(StackOp))
            {
                Push(StackOp, Infix[i]);
            }else
            {
                // 栈非空，依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若遇到'('或栈空，则停止。
                // 之后再把当前运算符入栈
                ElemType top;
                GetTop(StackOp, top);   // 获取栈顶运算符
                while (top != '(' && !StackEmpty(StackOp))  //若遇到'('或栈空，则停止
                {
                    // 依次弹出栈中优先级高于或等于当前运算符的所有运算符
                    // 例如扫描到'-'，优先级为1，StackOp中有'+'和'*'，优先级是1和2，>= '-'，所以这两个符号都会Pop，加入Postfix
                    if (JudgePriority(Infix[i]) <= JudgePriority(top))
                    {
                        ElemType temp;
                        Pop(StackOp, temp); // 弹出运算符
                        CharAddAfterString(temp, Postfix);
                    }else{
                        break; 
                    }
                    GetTop(StackOp, top);   // 获取栈顶运算符
                }
                // 之后再把当前运算符入栈StackOp
                Push(StackOp, Infix[i]);
            }
        }
    // -------------------------------------------
        // 遇到界限符
        // 遇到'('直接入栈，且'('不加入后缀表达式
        if (OpSign == "LeftBracket")
            Push(StackOp, Infix[i]);
    // -------------------------------------------
        // 遇到')'依次弹出栈内运算符，并把运算符加入后缀表达式，直到弹出'('为止，且'(', ')'不加入后缀表达式
        if (OpSign == "RightBracket")
        {
            ElemType temp;
            do
            {
                Pop(StackOp, temp); // 弹出运算符
                CharAddAfterString(temp, Postfix);
            } while (temp == '(');
            Pop(StackOp, temp); // 因为上一个循环在'('处停止，需要再把'('弹出，但是不加入表达式
        }
    // -------------------------------------------
    }
    // 处理完所有字符后，将栈内剩余运算符依次弹出，加入后缀表达式
    while (!StackEmpty(StackOp))
    {
        ElemType temp;
        Pop(StackOp, temp);
        CharAddAfterString(temp, Postfix);
    }
    return Postfix;
}
string JudgeOperation(ElemType ch){
    // 操作数
    if (ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch >= '0' && ch <= '9')
        return "Operand";
    // 运算符
    if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
        return "Operator";
    // 括号
    if (ch == '(')
        return "LeftBracket";
    if (ch == ')')
        return "RightBracket";
    return "InvalidInput";
}

int JudgePriority(ElemType ch)
{
    switch (ch)
    {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}
void CharAddAfterString(ElemType ch, string &S)
{
    string temp;
    temp.push_back(ch);
    S.append(temp);
}

#include 
#define MaxSize 50
using namespace std;
typedef char ElemType;  // ElemType定为char
// 顺序栈实现
typedef struct
{
    ElemType data[MaxSize];  // 存放栈中元素
    int top;    // 栈顶指针
}SqStack;
// 栈的基本操作
void InitStack(SqStack &S);
bool StackEmpty(SqStack S);
bool Push(SqStack &S, ElemType x);
bool Pop(SqStack &S, ElemType &x);
bool GetTop(SqStack S, ElemType &x);
// 中缀转后缀
string InfixConvertToPostFix(string Infix);
string JudgeOperation(ElemType ch);    // 判断ch字符类型
int JudgePriority(ElemType ch);     // 返回+-*/的优先级
void CharAddAfterString(ElemType ch, string &S);    // 把字符char加到string后

// -------------------------------------------
// main
int main()
{
    string Infix = "((15/(7-(1+1)))*3)-(2+(1+1))";
    string Postfix = InfixConvertToPostFix(Infix);
    cout << Postfix << endl;
    return 0;
}
// -------------------------------------------

// 初始化
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.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;
}
// 中缀转后缀
string InfixConvertToPostFix(string Infix)
{
    string Postfix = ""; // 输出串
    // 初始化操作符栈
    SqStack StackOp;
    InitStack(StackOp);
    // 遍历Infix
    // 从左到右扫描InifxS
    for (int i = 0; i < Infix.length(); i++)
    {
        string OpSign = JudgeOperation(Infix[i]);  // 判断当前扫描到的字符是哪一种类型
    // -------------------------------------------
        // 错误直接退出循环
        if (OpSign == "InvalidInput")
        {
            cout << "表达式有误！" << endl;
            break;
        }
    // -------------------------------------------
        // 遇到操作数，加入表达式Postfix内
        if (OpSign == "Operand")
            Postfix.append(Infix,i, 1); //把Infix，i位置起1个元素append到Postfix中
    // -------------------------------------------
        // 遇到运算符
        if (OpSign == "Operator")
        {
            // 栈空，不管什么运算符，直接入栈
            if (StackEmpty(StackOp))
            {
                Push(StackOp, Infix[i]);
            }else
            {
                // 栈非空，依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若遇到'('或栈空，则停止。
                // 之后再把当前运算符入栈
                ElemType top;
                GetTop(StackOp, top);   // 获取栈顶运算符
                while (top != '(' && !StackEmpty(StackOp))  //若遇到'('或栈空，则停止
                {
                    // 依次弹出栈中优先级高于或等于当前运算符的所有运算符
                    // 例如扫描到'-'，优先级为1，StackOp中有'+'和'*'，优先级是1和2，>= '-'，所以这两个符号都会Pop，加入Postfix
                    if (JudgePriority(Infix[i]) <= JudgePriority(top))
                    {
                        ElemType temp;
                        Pop(StackOp, temp); // 弹出运算符
                        CharAddAfterString(temp, Postfix);
                    }else{
                        break; 
                    }
                    GetTop(StackOp, top);   // 获取栈顶运算符
                }
                // 之后再把当前运算符入栈StackOp
                Push(StackOp, Infix[i]);
            }
        }
    // -------------------------------------------
        // 遇到界限符
        // 遇到'('直接入栈，且'('不加入后缀表达式
        if (OpSign == "LeftBracket")
            Push(StackOp, Infix[i]);
    // -------------------------------------------
        // 遇到')'依次弹出栈内运算符，并把运算符加入后缀表达式，直到弹出'('为止，且'(', ')'不加入后缀表达式
        if (OpSign == "RightBracket")
        {
            ElemType temp;
            do
            {
                Pop(StackOp, temp); // 弹出运算符
                CharAddAfterString(temp, Postfix);
            } while (temp == '(');
            Pop(StackOp, temp); // 因为上一个循环在'('处停止，需要再把'('弹出，但是不加入表达式
        }
    // -------------------------------------------
    }
    // 处理完所有字符后，将栈内剩余运算符依次弹出，加入后缀表达式
    while (!StackEmpty(StackOp))
    {
        ElemType temp;
        Pop(StackOp, temp);
        CharAddAfterString(temp, Postfix);
    }
    return Postfix;
}
string JudgeOperation(ElemType ch){
    // 操作数
    if (ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch >= '0' && ch <= '9')
        return "Operand";
    // 运算符
    if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
        return "Operator";
    // 括号
    if (ch == '(')
        return "LeftBracket";
    if (ch == ')')
        return "RightBracket";
    return "InvalidInput";
}

int JudgePriority(ElemType ch)
{
    switch (ch)
    {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}
void CharAddAfterString(ElemType ch, string &S)
{
    string temp;
    temp.push_back(ch);
    S.append(temp);
}