问题描述
“+”代表AND，“|”代表OR，如何基于这个两个运算符号写个类似四则运算优先处理“（）”内的逻辑？
A+B代表A and B；没毛病
A|B代表A或B；没毛病
很简单对吧？
那么((A+B)|C)+(D|(E+F))
(((A+B)|C)+(D|(E+F)))l(G+H)
怎么设计程序才能支持这样的输入呢?
解决思路
计算机组成原理里的栈
设计一个栈结构，从左到右将字符压入栈底，有左括号则直到遇到右括号才吐出来，并计算括号内内容，将结果继续压入栈，若没有左括号，则遇到两个值后吐出来计算，再压进去，直到完成所有字符读取。
最后在栈内的就是结果
代码编写
class andOrStack(object):
'''
A+B --> A and B
A|B --> A or B
purpose: get the final result
example: (T+F) == F
(T|F) == T
(T+F)|F == F
input: T means True
F means False
'''
def __init__(self, inputString):
print('addOrStack initialing')
self.inputString = inputString
self.stack = []
self.leftBrackets = 0 # 左括号数量
self.needManipulate = 0 # 是否需要处理运算
self.firstLetter = True
self.result = True
self.letterLen = len(self.inputString)
# 计算结果
result = self.getResult(self.inputString)
def manipulateStack(self, idx, letter):
print('leftBrackets now is {}'.format(self.leftBrackets))
if len(self.stack) == 0:
self.firstLetter = True
if idx+1 == self.letterLen and len(self.stack)==0:
if letter=='T':
print('result is True')
return True
if letter=='F':
print('result is False')
return False
print(idx, self.stack)
if self.firstLetter == True:
if letter=='T':
self.firstLetter = False
self.stack.append(True)
print('first T')
self.result = True
print(self.stack)
return None
if letter=='F':
self.firstLetter = False
self.stack.append(False)
self.result = False
return None
self.firstLetter = False
print(idx, self.stack)
# 计算字符
# 如果是左括号，则存入栈
if letter == '(':
self.stack.append(letter)
self.leftBrackets += 1
print('leftBrackets now is {}'.format(self.leftBrackets))
# 如果是右括号，则计算栈里的内容，并存入栈
if letter == ')':
aBool = self.stack.pop()
relationship = self.stack.pop()
bBool = self.stack.pop()
self.stack.pop() # 去掉左括号
self.leftBrackets -= 1
print('leftBrackets now is {}'.format(self.leftBrackets))
if relationship=='|':
b = aBool or bBool
self.result = b
if b==True:
self.manipulateStack(idx, 'T')
elif b==False:
self.manipulateStack(idx, 'F')
if relationship=='+':
b = aBool and bBool
if b==True:
self.manipulateStack(idx, 'T')
elif b==False:
self.manipulateStack(idx, 'F')
# 如果为T或者F，则查看左一是否为运算符
# 且左二是否为bool
if letter == 'T':
print('second T')
if self.needManipulate > 0 and self.leftBrackets==0:
aBool = True
relationship = self.stack.pop()
bBool = self.stack.pop()
print(aBool, relationship, bBool)
# 递归调用自身
if relationship=='|':
b = aBool or bBool
self.result = b
if b==True:
self.manipulateStack(idx, 'T')
elif b==False:
self.manipulateStack(idx, 'F')
if relationship=='+':
b = aBool and bBool
self.result = b
if b==True:
self.manipulateStack(idx, 'T')
elif b==False:
self.manipulateStack(idx, 'F')
self.needManipulate -= 1
else:
self.needManipulate += 1
letter = True
self.stack.append(letter)
if letter == 'F':
if self.needManipulate > 0 and self.leftBrackets==0:
aBool = False
relationship = self.stack.pop()
bBool = self.stack.pop()
# 递归调用自身
if relationship=='|':
b = aBool or bBool
self.result = b
if b==True:
self.manipulateStack(idx, 'T')
elif b==False:
self.manipulateStack(idx, 'F')
if relationship=='+':
b = aBool and bBool
self.result = b
if b==True:
self.manipulateStack(idx, 'T')
elif b==False:
self.manipulateStack(idx, 'F')
self.needManipulate -= 1
else:
self.needManipulate += 1
letter = False
self.stack.append(letter)
if letter == '|':
# 如果此时左边有没有左括号
if self.leftBrackets == 0:
self.needManipulate += 1
self.stack.append(letter)
else:
self.stack.append(letter)
if letter == '+':
# 如果此时左边有没有左括号
if self.leftBrackets == 0:
self.needManipulate += 1
self.stack.append(letter)
else:
self.stack.append(letter)
print(idx, self.stack)
def getResult(self, inputString):
'''
定义stack为list类型的栈
设计一个栈结构，
从左到右将字符压入栈底，
有左括号则直到遇到右括号才吐出来，
并计算括号内内容，将结果继续压入栈
若没有左括号，
则遇到两个值后吐出来计算，
再压进去，直到完成所有字符读取。
'''
for idx, letter in enumerate(inputString):
print(idx, letter)
self.manipulateStack(idx, letter)
print('final stack is:')
print(self.stack)
print('final result is:')
print(self.result)
return
if __name__=='__main__':
inputString = "(T+F)"
print('*************')
print("(T+F)")
c = andOrStack("(T+F)")
print('*************')
print('*************')
print("T+T")
c = andOrStack("T+T")
print('*************')
print('*************')
print('((T+F)|T)+(F|(T+F))')
c = andOrStack("((T+F)|T)+(F|(T+F))")
print('*************')
print('*************')
print('(((T+T)|F)+(T|(F+F)))|(T+F)')
c = andOrStack("(((T+T)|F)+(T|(F+F)))|(T+F)")