问题描述

“+”代表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)")