解一元一次方程伪代码:
class TreeStructure
expression:string ->表达式
left:TreeStructure ->左边的树结构
right:TreeStructure ->右边的树结构
state=0:string ->访问状态
parent:TreeStructure ->指向于父节点
operator:string ->操作符
result:int ->结果
def 栈对字符串根据符号进行分割构造成树（传入一个字符变量str）
声明一个名为root的树，将str填入其构造方法
声明一个栈并将root树压入栈中
while 栈不为空
声明一个名为current的变量并将栈中第一个赋值给它
调用方法查找current的expression中符号所在位置获取返回值并命名为num
IF num为-1
IF 将第一个“(”与最后一个“)”将其消除掉
current出栈
创建一个变量命名为left，并将其出去括号的字符串填入构造方法
将当前出栈的current赋值给left的parent
将left赋值给root树的左树
将left压入栈中
ELSE
current出栈
将当前current对应的expression赋值给它的result属性
ELSE IF num大于0
current出栈
根据下标0到返回值，来截取字符串，得到符号左边的字符串 = leftStr
根据返回值+1到字符串长度，来截取字符串，得到符号右边的字符串 = rightStr
left = new TreeStucture(leftStr)
right = new TreeStucture(rightStr)
将当前num对应的符号赋值给current的operator
将current加入到left.parent作为父节点，并赋值给root的左树
将current加入到right.parent作为父节点，并赋值给root的右树
将right树压入栈中
将left树压入栈中
def 根据树后序遍历出来的结果计算表达式(传入已经构建好的字符串树变量root)
声明一个stack栈并将root压入栈中
while stack栈不为空
current 获取栈顶的树并赋值作为当前的树
IF current的state等于他子节点个数时
IF current.opteator不为空时
对current的opteator运算符进行判断后将current的左右子节点的result进行运算
ELSE IF current只有一个子节点
将current的子节点的result赋值给current的result
将current出栈
IF 将当前current的parent不为空
父节点中state+=1
ELSE
IF 左树不为空
将左树压入stack栈中
IF 右树不为空
将右树压入stack栈中
print(root.result)
def 查找当前字符中的符号所在位置(传入一个字符串)
FOR 对字符串长度进行循环
得到当前下标的单个字符
IF 字符等于"("
计数+1
ELSE IF 字符等于")"
计数-1
ELSE IF 字符=="+" 与 计数==0
返回当前下标
FOR 以字符串最后一个字符开始进行循环
得到当前下标的单个字符
IF 字符等于"("
计数+1
ELSE IF 字符等于")"
计数-1
ELSE IF 字符等于"-" 与 计数==0
返回当前下标
FOR 对字符串长度进行循环
得到当前下标的单个字符
IF 字符等于"("
计数+1
ELSE IF 字符等于")"
计数-1
ELSE IF （字符等于"*" 或 字符等于"/"） 与 计数==0
返回当前下标
返回-1
Python实现代码：
class Stack(object): def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def peek(self):
return self.items[len(self.items) – 1]
def size(self):
return len(self.items)
def push(self, item):
self.items.append(item)
def pop(self): return self.items.pop()
class TreeNode(object): def __init__(self, x): self.expression = x self.left = None self.right = None self.parent = None self.state = 0 self.operator = None self.result= None
def structuralTree(str): root = TreeNode(str) stack = Stack() stack.push(root) while stack.size() >0 : current = stack.peek() nums = strToTree(current.expression) if nums == -1 : if current.expression.startswith("(") and current.expression.endswith(")") : current=stack.pop() expression = current.expression[1:len(current.expression)-1]; left = TreeNode(expression) left.parent = current current.left = left stack.push(left) else: current=stack.pop() current.result=current.expression elif nums > 0 : current=stack.pop() leftStr = current.expression[0:nums] rightStr = current.expression[nums+1:len(str)] operator = current.expression[nums:nums+1] current.operator = operator leftTree = TreeNode(leftStr) rightTree = TreeNode(rightStr) leftTree.parent = current rightTree.parent = current current.left = leftTree current.right = rightTree stack.push(rightTree) stack.push(leftTree) return root
def strToTree(str): num = 0 for i in range(len(str)): if str[i] == "(": num += 1 elif str[i] == ")": num -= 1 elif str[i] == "+" and num == 0 : return i for i in range(len(str[::-1])): if str[i] == "(": num += 1 elif str[i] == ")": num -= 1 elif str[i] == "-" and num==0 : return i for i in range(len(str)): if str[i] == "(": num += 1 elif str[i] == ")": num -= 1 elif (str[i] == "*" or str[i] == "/") and num==0 : return i return -1
def postOrder(root): stack = Stack() stack.push(root) while stack.size() >0 : current = stack.peek() num = 0 if current.left != None: num += 1 if current.right != None: num += 1 if current.state == num : if current.operator != None : if current.operator == "+": current.result = int(current.left.result) + int(current.right.result) elif current.operator == "-": current.result = int(current.left.result) – int(current.right.result) elif current.operator == "*": current.result = int(current.left.result) * int(current.right.result) elif current.operator == "/": current.result = int(current.left.result) / int(current.right.result) elif current.left != None and current.right == None: current.result=current.left.result stack.pop() if current.parent != None : current.parent.state += 1 else: if current.left != None: stack.push(current.left) if current.right != None: stack.push(current.right) print(root.expression,"=",root.result)
root = structuralTree("((2+3)/5-(2+3)*4-(3-3))") postOrder(root)
神龙|纯净稳定代理IP免费测试>>>>>>>>天启|企业级代理IP免费测试>>>>>>>>IPIPGO|全球住宅代理IP免费测试
