|
发表于 2022-6-3 14:46:20
|
显示全部楼层
本楼为最佳答案
来晚了,前段时间有点忙
看不懂你那个图片是怎么表示二叉树的
下面这个代码创建出了这颗树,你想要怎么输出就自己写代码吧
- #!/usr/bin/env python
- #coding=utf-8
- from ctypes import cdll
- from ctypes.util import find_library
- from ctypes import c_void_p, c_int, byref
- import sys
- libc = cdll.LoadLibrary(find_library('c'))
- stdin = c_void_p.in_dll(libc, 'stdin')
- def fgetc(stream):
- return libc.fgetc(stream)
- def ungetc(ch, stream):
- return libc.ungetc(ch, stream)
- # token
- # [[symbol, value], lchild, rchild]
- last_token = None
- ERROR = 256
- NUM = 257
- EOF = -1
- def error(value):
- return [[ERROR, value], None, None]
- def isdigit(ch):
- return ch >= ord('0') and ch <= ord('9')
- def get_token():
- global last_token
- if last_token:
- result = last_token
- last_token = None
- return result
- ch = fgetc(stdin)
- if ch in [ord(i) for i in [' ', '\t', '\v', '\f']]:
- return get_token()
- if isdigit(ch):
- ungetc(ch, stdin)
- num = c_int()
- libc.fscanf(stdin, b'%d', byref(num))
- return [[NUM, num.value], None, None]
- return [[ch, None], None, None]
- def unget_token(token):
- global last_token
- last_token = token
- def factor():
- token = get_token()
- if token[0][0] == NUM: return token
- if token[0][0] == ord('-'):
- token[1] = factor()
- if token[1][0][0] == ERROR: return token[1]
- return token
- if token[0][0] != ord('('): return error(token[0][1])
- token = expression()
- if token[0][0] == ERROR: return token
- temp = token
- token = get_token()
- if token[0][0] != ord(')'): return error(token[0][1])
- return temp
- def term():
- token = factor()
- if token[0][0] == ERROR: return token
- a = token
- token = get_token()
- if token[0][0] != ord('*') and token[0][0] != ord('/'):
- unget_token(token)
- return a
- op = token
- token = term()
- if token[0][0] == ERROR: return token
- b = token
- op[1] = a
- op[2] = b
- return op
- def expression():
- token = term()
- if token[0][0] == ERROR: return token
- a = token
- token = get_token()
- if token[0][0] != ord('+') and token[0][0] != ord('-'):
- unget_token(token)
- return a
- op = token
- token = expression()
- if token[0][0] == ERROR: return token
- b = token
- op[1] = a
- op[2] = b
- return op
- def do_error():
- print('错误的表达式!', file = sys.stderr)
- while True:
- token = get_token()
- if token[0][0] == ord('\n'): break
- def val(tree):
- if tree[0][0] == NUM: return tree[0][1]
- if tree[0][0] == ord('+'): return val(tree[1]) + val(tree[2])
- if tree[0][0] == ord('*'): return val(tree[1]) * val(tree[2])
- if tree[0][0] == ord('/'): return val(tree[1]) / val(tree[2])
- if tree[0][0] == ord('-'):
- return -val(tree[1]) if tree[2] == None else val(tree[1]) - val(tree[2])
- raise "未知的运算符!"
- def line():
- token = get_token()
- if token[0][0] == ord('\n'): return
- unget_token(token)
- token = expression()
- if token[0][0] == ERROR:
- do_error()
- return
- result = token
- token = get_token()
- if token[0][0] == ord('\n'):
- #print(result)
- print('>>> ' + str(val(result)))
- return
- do_error()
- def lines():
- token = get_token()
- unget_token(token)
- if token[0][0] == EOF:
- return
- line()
- lines()
- return
- def start():
- lines()
- token = get_token()
- if token[0][0] == EOF: return True
- return False
- print(start())
复制代码
下面说一下这个代码的思路
1. 先写出这个语言(表达式)的文法
- start: lines (EOF);
- lines: (EMPTY)
- | line lines
- ;
- line: expression '\n' {print(expression);}
- | '\n'
- | (ERROR) {printf("错误的表达式!\n");}
- ;
- expression: term
- | expression '+' term {$$ = $1 + $3;}
- | expression '-' term {$$ = $1 - $3;}
- ;
- term: factor
- | term '*' factor {$$ = $1 * $3;}
- | term '/' factor {$$ = $1 / $3;}
- ;
- factor: NUM
- | '-' factor {$$ = -$2;}
- | '(' expression ')' {$$ = $2;}
- ;
复制代码
2. 用递归下降分析,照着这个文法写代码
3. 调试,其实应该是边写代码边调试,写一点调试一点
|
|