美文网首页Qt学习
13_计算器核心解析算法(中)

13_计算器核心解析算法(中)

作者: 编程半岛 | 来源:发表于2018-01-19 19:48 被阅读15次

声明:此文章仅是本人在学习狄泰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. 小结

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

相关文章

  • 13_计算器核心解析算法(中)

    声明:此文章仅是本人在学习狄泰QT实验分析课程所做的笔记,文章中包含狄泰软件资料内容,一切版权归狄泰软件所有!实验...

  • 12_计算器核心解析算法(上)

    声明:此文章仅是本人在学习狄泰QT实验分析课程所做的笔记,文章中包含狄泰软件资料内容,一切版权归狄泰软件所有!实验...

  • 学习资料汇总

    GeoHash核心原理解析 GeoHash算法学习讲解、解析及原理分析

  • iOS动画

    CoreAnimation 问题不在动画代码上,在动画算法上 CoreAnimation(超详细解析核心动画)C...

  • Glide解析(一) - LruCache

    本文介绍的内容有 LruCache算法思想介绍 v4包中LruCache中源码解析 LruCache算法思想介绍 ...

  • 区块链资源

    书籍: 《区块链项目开发指南》 《区块链核心算法解析》 《区块链:技术驱动金融》 《区块链革命:比特币底层技术如何...

  • 梯度下降解决线性回归,以及自适应学习率设置

    线性回归一般用于预测:比如股票涨停梯度下降是机器学习中最核心的优化算法 函数解析:np.random.normal...

  • 排序算法:计数排序O(n+m)

    核心思想 计数排序不是基于比较的排序算法,算法的核心有3点:统计原数组中每个元素出现的次数。以原数组中的元素为下标...

  • underscore中rest参数实现原理

    underscore中rest参数实现原理 核心函数: restArgs方法 源码: 实例: 解析: 在源码中,_...

  • 2020-06-19 顿悟

    做事,无论是工作中的编程,还是生活中的琐事 事情的处理,核心是思路 就如算法是程序的核心,算法是思路的体现 一个优...

网友评论

    本文标题:13_计算器核心解析算法(中)

    本文链接:https://www.haomeiwen.com/subject/ldfaoxtx.html