C++实现对数学基本运算表达式的解析

前段时间在LeetCode上刷题,遇到了很多涉及对字符串进行解析的题目。可能是出于这个原因,最近迷恋上了字符串的解析问题。数学基本运算表达式的解析就涉及这类问题。所谓数学基本运算表达式的解析就是指给定一个表达式字符串,如1 + 13 * 9,对这个字符串进行解析,从而得到这个表达式的运算结果。(数学基本运算表达式也就是只用加减乘除进行计算的数学表达式)

其实站在我的角度来看,我觉得对数学基本运算表达式的解析还是有一定难度的。因为如果一开始没有正确的思路,我们是很难找到这个问题的着手点的,毕竟解析数学基本运算表达式需要考虑到的问题是有点多的,以下,我把其中主要的问题列举出来:

  1. 乘除法优先计算
  2. 括号里的内容优先计算
  3. 表达式中的数字前可能存在正负号

这些问题如果得不到恰当的处理,就会使解析过程失败。

在实现解析数学基本运算表达式之前,我们首先得弄清楚哪些表达式是合法的,哪些表达式是不合法的。以下我将列举C/C++等语言中,一些合法与不合法的表达式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 合法 */
7 + 22 + 7 * 27
6 + -13 * 23 / -30 / 35
24 - +34
10 + (3 * 9) / 8
/* 不合法 */
abc + 123 // abc不是数字
1 + 2 * // *后缺少数字
6 + + 12 // 不能连用加号
8 - - 17 // 不能连用减号
32 + () - 4 // 括号中没有内容
(0 + 5)) * 7 // 右括号多了一个
((11 + 9) / 2 // 左括号多了一个

不排除有一些编程语言支持上述所说的部分或者全部不合法表达式,但这里我们先使用C/C++标准。

阅读全文 →

分享到 评论

NodeJs开发简易的Http本地服务器

第一次接触本地服务器是很早之前因为Js学到Ajax部分,需要通过发送Http请求读取本地文件。

网上实用的本地服务器有很多,如Apache,XAMPP等。不过在我平时开发的过程中,其实用不了太多功能,多数情况下只需要我们的服务器根据请求从本地读取文件,不大必要使用上述的大型本地服务器,所以在我接触NodeJs后,索性用NodeJs写了一个Http本地服务器,连同空行总共69行代码。

运行效果图之一

(成功开启服务器后的效果如上图所示)

阅读全文 →

分享到 评论

【译】碰撞检测之分离轴定理算法讲解

本文翻译自@sevenson的文章Separating Axis Theorem (SAT) Explanation 。原文作者用的是ActionScript 3来编写算法,不过文中主要讲述的还是算法原理,我想一旦算法原理被我们掌握了,选择什么编程语言来实现算法都是次要的事情了。
本人并非英文专业,所以文中翻译得有不妥或疏漏之处,欢迎各位指正,谢谢!


正文如下:

多边形碰撞

分离轴定理(英文简称SAT)是一项用于检测凸多边形碰撞的技术。

我绝不是这个方面的专家,但当检测碰撞的需求出现在我面前之后,我做了大量的阅读并最终在ActionScript 3中实现了它。

我想,我应该把我所学到的分享给大家,希望大家不会在这方面被坑得很惨:)

阅读全文 →

分享到 评论

分享新作 - 虐心小游戏Flying Stone

游戏简介

Flying Stone是一款益智类物理游戏。游戏中,玩家通过轻敲屏幕,抛出系在旋转杆上的石头来攻击飞出的小鸟,以此得分。不同难度的小鸟,击中后得分也有所不同。游戏限时90秒,游戏结束后会上传你的得分,并得到你的全世界排行。

本游戏目前支持Android版和在线版。

Flying Stone

如何开始

访问游戏主页,你可以在其中找到所需的版本:

http://wyh.wjjsoft.com/pages/flying_stone/

阅读全文 →

分享到 评论

挑战速度,2小时完成HTML5拼图小游戏

初学lufylegend.js之日,我用lufylegend.js开发了第一个HTML5小游戏——拼图游戏,还写了篇博文来炫耀一下:HTML5小游戏《智力大拼图》发布,挑战你的思维风暴。不过当时初学游戏开发,经验浅薄,所以没有好好专研游戏里的算法和代码的缺陷,导致游戏出现了很多bug,甚至拼图打乱后很可能无法复原。最近经常有朋友问起这个游戏,希望我能把代码里的bug改一下方便初学者学习,顺便我也打算测试一下自己写这种小游戏的速度,所以就抽出了一些时间将这个游戏从头到尾重新写了一遍,计算了一下用时,从准备、修改素材到最后完成游戏,一共用了大约2h的时间。

以下是游戏地址:

http://yuehaowang.github.io/games/puzzle/

这是我的游戏记录,欢迎各位挑战:

我的纪录

接下来就来讲讲如何开发完成这款游戏的。(按“编年体”)

阅读全文 →

分享到 评论

算法研究:利用Python解决数学计数原理问题

最近数学修行到“计数原理”部分,前几天做作业时遇到这样一道数学题:

用四种不同颜色给三棱柱六个顶点涂色,要求每个点涂一种颜色,且每条棱的两个端点涂不同颜色,则不同的涂色方法有多少种?
题目配图

当我看完题目后,顿时不知所措。于是我拿起草稿纸在一旁漫无目的地演算了一下,企图能找到解决方法。结果一无所获。今天终于等到放假了,于是打算通过程序算法解决这个问题。经过2个多小时的研究,终于完成了代码,并求得了答案。

由于Python写起来比较方便而且本人比较喜欢Python的语法,所以研究算法时我通常采用Python,此次也不例外。以下就是整个算法的实现过程。

阅读全文 →

分享到 评论

证明:sin'x = cosx

初三将近毕业的时候老爸给我买了几本数学相关的书籍。还把他的大学教材翻出来给我看,希望我去提前学习高等数学。很遗憾,当时的我对于这些东西完全不感兴趣,所以就不屑一顾,往书架上一扔就是两年。不久前,自己在数学教科书上看到了积分。书中运用积分的知识求得了一个曲边形的面积。当时我就傻眼了,什么!数学居然可以这么神奇。我这才意识到自己的无知,并且激起了我强烈的研究数学的欲望。这段时间里,我相继学习了导数和定积分,越发觉得数学的高深,决定提前学习大学里的高等数学。

大学课程中,第一个难题就是极限。有了它,才有导数、积分……

经过一个半月的课余时间学习,我大致地掌握了极限的一些知识。于是我决定使用它来解决一个我在导数学习过程中的一个问题:证明sin’x = cosx。

以下是我经过研究,得出的证明过程。

证明过程

首先根据导数定义,我们得到以下几个式子:

证明过程 之一

阅读全文 →

分享到 评论