声明：此文章仅是本人在学习狄泰QT实验分析课程所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4

1. 中缀转后缀

中缀表达式转后缀表达式的过程类似编译过程

• 四则运算表达式中的括号必须匹配
• 根据运算符优先级别进行转换
• 转换后的表达式中没有括号
• 转换后可以顺序的计算出最终结果

转换过程：

• 当前元素e为数字：输出
• 当前元素e为运算符：
  1） 与栈顶运算符进行优先级比较
  2）小于等于：将栈顶元素输出，转1
  3） 大于：将当前元素e入栈
• 当前元素e为左括号：入栈
• 当前元素e为右括号：
  1） 弹出栈顶元素并输出，直至栈顶元素为左括号
  2） 将栈顶的左括号从栈中弹出

转换过程伪代码：

转换关键点
验证表达式中的括号能过左右匹配！！！

2. 括号匹配算法

合法的四则运算表达式中：
1）括号匹配成对出现
2） 左括号必然先于右括号出现

编程说明：匹配算法

bool QCalculatorDec::match(QQueue<QString>& exp)
{
    bool ret = true;
    QStack<QString> stack;

    for(int i = 0; i < exp.length(); i++)
    {
        if( isLeft(exp[i]) )
        {
            stack.push(exp[i]);
        }
        else if (isRight(exp[i]))
        {
            if( !stack.isEmpty() && isLeft(stack.top()) )
            {
                stack.pop();
            }
            else
            {
                ret = false;
                break;
            }
        }
    }

    return ret;
}

编程说明：中缀表达式转换后缀表达式算法

bool QCalculatorDec::transform(QQueue<QString>& exp, QQueue<QString>& output)
{
    bool ret = match(exp);
    QStack<QString> stack;

    output.clear();

    while ( ret && !exp.isEmpty() )
    {
        QString e = exp.dequeue();

        if( isNumber(e) )
        {
            output.enqueue(e);
        }
        else if( isOperator(e) )
        {
            while( !stack.isEmpty() && (priority(e) <= priority(stack.top())) )
            {
                output.enqueue(stack.pop());
            }

            stack.push(e);
        }
        else if( isLeft(e) )
        {
            stack.push(e);
        }
        else if( isRight(e))
        {
            while( (!stack.isEmpty()) && (!isLeft(stack.top())) )
            {
               output.enqueue(stack.pop());
            }

            if( !stack.isEmpty())
            {
                stack.pop();
            }
        }
        else
        {
            ret = false;
        }
    }

    while( !stack.isEmpty())
    {
        output.enqueue(stack.pop());
    }

    if( !ret )
    {
        output.clear();
    }

    return ret;
}

3. 小结

• 后缀表达式是程序计算复杂表达式的基础
• 中缀表达式到后缀表达式的转换是基于栈数据结果的
• 转换过程能够发现表达式中的语法错误