引入
在20世纪30年代,波兰逻辑学家扬·卢卡西维茨(Jan Łukasiewicz),发明了一种将所有操作符置于操作数的后面
,因此也被称为后缀表示法。我们称之为逆波兰记法
。逆波兰记法不需要括号来标识操作符的优先级。
逆波兰表示法
上面的引入感觉很高大上,我们来个例题,对于解
$(1-2)\times (4+5)$
连小朋友都知道,先算括号里面的,再算括号外面的,最后结果相乘。
如果计算机来解题的话,就会用很多 if…else… 进行判断,显然对于我们人类方便的括号优先级表达法,对计算机不那么友好。
那么能不能对计算机友好一点?逆波兰表达式出现了,对于上面的问题:
普通式为:$(1-2)\times (4+5)$
逆波兰表达式为:$12-45\times$
基本的转换方法如下
- 所有数字从左到右写,位置不用动
- 遇到括号,先写出括号内的数字
- 然后在数字后面,以先乘除后加减的方式写出括号内的运算符
- 然后继续写数字,直到所有数字写完
- 然后在数字后面,以先乘除后加减的方式写出剩余的运算符
几个例子
$a+b$ 转换为:$ab+$
$a+(b-c)$ 转换为:$abc-+$
$a+(b-c) \times d$ 转换为:$abc-d \times+$
$a+b \times (b-c)$ 转换为:$adbc- \times +$
主判断逻辑
栈的创建、初始化、push、pop、length等操作我就不说了,主要讲这个逆波兰的判断。对了,栈内只存符号。
首先判断数字
如果输入的是数字
- 如果是0~9之间的数字,就直接输出
- 然后获取下一个输入的值
- 如果还是数字,就直接输出
- 如果不是数字,那就输出空格。
- 这样就完成了判断数字位数的问题。
判断括号
- 如果输入了反括号,那就证明括号内的内容结束了
- 我们要把括号内的符号提取出来
- 没有提取到正括号,那就继续提取里面的符号
判断加减
如果栈内没有符号
- 输入的如果是加号或者减号
- 如果栈是空栈,那就压入符号,然后继续接收输入
如果栈内本身有符号
- 那就先把符号取出来
- 如果是正括号,那没事,证明要压入的符号是括号内的运算符
- 直接压入符号即可
- 如果不是正括号,那就直接把里面的符号输出,因为有新的符号了
判断
如果栈不为空并且也不是正括号的话,那就证明栈里面还有运算符,并且这个运算符不是括号内的运算符
判断乘除
- 如果符号不是
+ -
,是* / (
的话 - 那就直接压栈
判断结束
- 如果输入的是 # 号的话
- 那就直接 break 跳出循环
啥都不是
- 如果输入的是非法字符,则输出错误
继续循环
- 如果输入的是符号且不是非法字符。
- 那就继续接收新的值,继续执行循环。
代码实现
1 |
|
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。