中缀转前缀


# infix [] -> 中缀表达式 ; s2[] -> 栈的顺序表 ; top2 -> 栈顶指针 ; len表达式长度
void infixToPostFix(char infix[ ], char s2[ ], int &top2, int len)
{
    char s1[maxSize];       #s1辅助栈
    int top1 = -1;
    int i = len-1;
    while(i >= 0)
    {
        if('0' <= infix[i] && infix[i] <= '9')
        {
            s2[++top2] = infix[i];
            --i;
        }
        else if(infix[i] == ')' )
        {
            s1[++top1] = ')';
             --i; 
        }
        else if (infix[i] == '+' || infix[i] == '-' ||
                    infix[i] == '*' || infix[i] == '/')
        {
            if(top1 == -1 || s1[top1] == ')' ||      #当栈为空
                getPriority(infix[i]) >= getPriority(s1[top1]))     #当前优先级 >= 栈顶优先级
            {
                s1[++top1] = infix[i];
                --i;
            }
            else
                s2[++top2] = s1[top1--];      #将运算符入栈到s2中
        }
        else if(infix[i] == '(')      #当遇到左括号
        {
            while(s1[top1] != ')')
                s2[++top2] = s1[top1--];
            --top1;
            --i;
        }
    }
    while(top1 != -1)
        s2[++top2] = s1[top--];
}

上一篇:数据结构与算法_02堆栈


下一篇:Kotlin学习:第九章使用infix函数构建更可读的语法