数据结构 实验3

def calc(x,c,y):# 计算表达式 x@y if c=='+': return x+y if c=='-': return x-y if c=='*': return x*y if c=='/': return x/y def isdigit(c):# 判断字符 c 是不是数字 t=ord(c) return t>=ord('0') and t<=ord('9') comp={'#':-1,'(':0,')':0,'+':1,'-':1,'*':2,'/':2} # 规定运算符的优先级 op=[] # 运算符栈 op.append('#') # 先放一个优先级最低的符号，便于后续处理 num=[] # 数栈 k=input() # 原始表达式串 s=[] # 处理后的串 flag=0 # 当前位是否为数字 x=0 # 要把连续的字符型的数字转化为数 for i in range(len(k)):# 将连续数字转化为数，符号则不作处理，放入 s 串中 if isdigit(k[i]): x=x*10+int(k[i]) flag=1 if not isdigit(k[i]): if flag==1: s.append(x) flag=0 x=0 s.append(k[i]) continue if i==len(k)-1: if flag==1: s.append(x) s.append('#') for i in range(len(s)): if type(s[i])==type(1): # 如果当前是数 num.append(s[i]) # 则放入数栈 else: # 如果是运算符 if comp[s[i]]>comp[op[-1]]: # 当前运算符优先级大于栈顶符优先级则入栈 op.append(s[i]) else: if s[i]=='(': # 左括号直接入栈 op.append(s[i]) continue if s[i]==')': # 遇到右括号则需一直处理至左括号 while op[-1]!='(': y=num.pop() x=num.pop() num.append(calc(x,op.pop(),y)) op.pop() else: while comp[s[i]]<=comp[op[-1]]: # 若当前位优先级不大于栈顶符优先级则出栈 if op[-1]=='#': # 遇到 '#' 则结束 break y=num.pop() x=num.pop() num.append(calc(x,op.pop(),y)) op.append(s[i]) print(num[-1]) # 输出数栈里剩下的唯一元素 def move(cnt,A,B,C): # 将 cnt 个盘 A->C，以 B 为中转 if cnt==1: # 递归边界 print("%d %c %c"%(cnt,A,C)) return move(cnt-1,A,C,B) # 先把上面 cnt-1 个 A->B print("%d %c %c"%(cnt,A,C)) # 再挪最下面那个盘 A->C move(cnt-1,B,A,C) # 再把刚刚那 cnt-1 个盘 B->C n=int(input()) move(n,'A','B','C')