高级编程通关练习题 #2：解析数学表达式

June 10, 2021Posted inAdvanced Level Programming Problems
以字符串形式给定一条有效的数学表达式，使用字符串解析的方式计算该表达式的结果。注意不能使用 eval 方法来得出结果。 表达式的规则如下： 表达式里可能出现的数学操作符为：加（+）、减（-）、乘（*）、除（/）可能的数值包括正负数和小数需要分析可能出现的多重小括号，譬如：（15 * （9.5 + 6）- -10）/ 4 输入样例： "(-7 * -(16 / 4)) * (9.5 - 4.5)" 输出样例： 140.0 算法思路： 方法一：可以采用数据结构stack来逐一处理每个字符如果字符是数字或小数点，则添加到到临时字符串变量A中。如果字符不是数字或者小数点，则把临时变量A中的字符串转换成数字，然后压栈。如果是字符是数学操作符加减乘除或左小括号，就把该字符压栈。如果字符是右小括号，那么需要从栈顶弹出数值和操作符保存到临时变量B，直到遇到左小括号为止，然后将字符串B做数学计算。数学计算的顺序如下：先计算除法，然后计算乘法，接下来计算减法，最后计算加法。字符串循环读取完毕后，检查stack栈内是否为空，如果不为空则需要将栈内内容重复上面第三项操作。方法二：使用正则表达式来解析字符串以左右小括号为标志先后解析需要计算的表达式提取数学操作符和数值后做相应处理

入门级编程通关练习题 #9 – 匹配字符串

May 20, 2021Posted inEntry Level Programming Problems
给定一个字符串，里面的字符都是由括号组成：（）、[ ]、{ }。检查这个字符里面的括号是否匹配，譬如字符串 ”[ ( ) ] { }“ 是匹配的，而字符串”] [ “是不匹配的。 输入样例： "[({})](]" 输出样例： False 算法思路： 这是典型使用stack数据类型的练习题。每次拿到一个括号，可以和栈顶的字符进行匹配。能够匹配的一对括号就可以消去，如果不能匹配或者栈内为空则压栈。最后栈内如果还有剩余括号表明该字符串里面的括号不匹配，如果为空则表明匹配。