• python实现中缀表达式转后缀表达式


    前缀、中缀、后缀表达式(逆波兰表达式)

    前缀表达式称为波兰表达式,前缀表达式的运算符位于操作符之前

    举例说明:(3+4)x 5 – 6 对应的前缀表达式就是- X + 3 4 5 6

     

    中缀表达式转为后缀表达式

    具体步骤:(注意括号不算运算符)

    1. 初始化两个栈,其中运算符栈s1和存储中间结果的栈s2
    2. 从左到右进行扫描中缀表达式
    3. 遇到操作符将其压进s2
    4. 遇到运算符,比较其与s1栈顶运算符的优先级:
    1. 如果s1为空,或者栈顶运算符为左括号,则直接将此运算符压进栈中
    2. 否则,若优先级比栈顶运算符的高,也将运算符压入s1
    3. 否则,将s1栈顶的运算符弹出并压入到s2中,再次转到第一小步中与s1中新的栈顶运算符相比较。

    5.遇到括号时:

    1. 如果是左括号,直接压入s1中
    2. 如果是有括号,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃

    6. 重复步骤2至5,直到表达是的最右边

    7. 将s1中剩余的运算符依次弹出并压入s2

    8. 依次弹出s2中的元素并输出,结果的逆序即中缀表达式对应的后缀表达式

    1. # 中缀表达式 ---> 后缀表达式
    2. # 1 + ((2+3)*4) - 5 ----> 1 2 3 + 4 * + 5 -
    3. class ArrayStack2:
    4. def __init__(self,masSize):
    5. self.maxsize = masSize
    6. self.stack = []
    7. self.top = -1
    8. # 判断栈是不是 满的
    9. def isFull(self):
    10. return self.top == self.maxsize - 1
    11. # 判断栈是不是空的
    12. def isEmpty(self):
    13. return self.top == -1
    14. # 将数据压入栈中
    15. def push(self,value):
    16. if self.isFull():
    17. print("栈已经满了!")
    18. return
    19. self.top = self.top + 1
    20. self.stack.append(value)
    21. # 将栈中的数据进行删除
    22. def pop(self):
    23. if self.isEmpty():
    24. print("栈已经是空的了,没法执行出栈操作!")
    25. return
    26. value = self.stack.pop()
    27. self.top = self.top - 1
    28. return value
    29. # 显示栈的内容,需要先从栈顶显示数据
    30. def showStack(self):
    31. if self.isEmpty():
    32. print("栈已经是空的了,没法执行显示操作!")
    33. return
    34. i = self.top
    35. while i > -1:
    36. print("栈中存在的数据:",self.stack[i])
    37. i = i -1
    38. # 返回运算法的优先级 有程序员决定 优先级使用数字来表示,数字越大优先级越高
    39. def priority(self,oper):
    40. if (oper == "*" or oper == "/"):
    41. return 1
    42. elif (oper == "+" or oper == "-"):
    43. return 0
    44. else:
    45. return -1
    46. # 判断是不是一个运算法
    47. def isOper(self,val):
    48. return val == "*" or val == "/" or val == "+" or val =="-"
    49. def isyunsuan(self,val):
    50. return val == "(" or val == ")"
    51. # 进行计算
    52. def cal(self,num1,num2,oper):
    53. if oper == "+":
    54. return num1 + num2
    55. elif oper == "-":
    56. return num2 - num1 # 注意顺序
    57. elif oper == "*":
    58. return num1 * num2
    59. elif oper == "/":
    60. return num2 / num1
    61. # 只返回最后的一个元素,但是并不是删除最后 一个元素
    62. def peek(self):
    63. return self.stack[self.top]
    64. class Infixtohouzhui:
    65. def __init__(self,expression = "1+((2+3)*4)-5"):
    66. self.expression = expression
    67. self.s1 = ArrayStack2(20)
    68. self.s2 = [] # 直接使用list比较好
    69. self.flag = 0
    70. self.index = 0
    71. self.data = 1
    72. self.keepnum = 0
    73. def change(self):
    74. while self.index <= len(self.expression) - 1:
    75. if self.s1.isOper(self.expression[self.index]) == False and self.s1.isyunsuan(self.expression[self.index]) == False:
    76. self.keepnum = self.expression[self.index]
    77. while True:
    78. if self.index + self.data <= len(self.expression) - 1:
    79. if (self.s1.isOper(self.expression[self.index + self.data])) == False and self.s1.isyunsuan(self.expression[self.index + self.data]) == False:
    80. self.flag = 1
    81. self.keepnum = self.keepnum + self.expression[self.index+self.data]
    82. self.data = self.data + 1
    83. else:
    84. break
    85. else:
    86. break
    87. self.s2.append(self.keepnum)
    88. self.keepnum = ""
    89. elif self.expression[self.index] == "(":
    90. self.s1.push(self.expression[self.index])
    91. # 如果是有括号,就将s1中的运算符,压到s2中,知道遇到左括号为止
    92. elif (self.expression[self.index]) == ")":
    93. while (self.s1.peek())!="(":
    94. self.s2.append(self.s1.pop())
    95. self.s1.pop() # 将s1中的左括号要删除掉
    96. else:
    97. # 当s1的栈顶运算符大于新来的运算符 将s1的栈顶运算符放到s2中,然后不停的比较
    98. while (self.s1.isEmpty() == False and self.s1.priority(self.s1.peek())>=self.s1.priority(self.expression[self.index])):
    99. self.s2.append(self.s1.pop())
    100. self.s1.push(self.expression[self.index])
    101. if self.flag:
    102. self.index = self.index + self.data
    103. self.flag = 0
    104. self.data = 1
    105. else:
    106. self.index = self.index + 1
    107. while self.s1.isEmpty() == False:
    108. self.s2.append(self.s1.pop())
    109. return self.s2
    110. if __name__ == '__main__':
    111. ll = Infixtohouzhui()
    112. print(ll.change())

  • 相关阅读:
    F检验临界值表(Frideman检验表)
    基于FTP协议的文件上传与下载
    简单Wordpress小工具开发
    vue拦截器是什么,如何使用
    安装RocketMq流程及踩坑
    BPF 调度器 sched_ext 实现机制、调度流程及样例
    007 个人博客系统
    深耕物料处理赛道,宏工科技助力涂料绿色自动化生产
    浏览器中的原生base64方法
    Util应用框架Web Api开发环境搭建
  • 原文地址:https://blog.csdn.net/weixin_44911037/article/details/128129924