求救！！！！谢谢大家
设计一个python程序，它可以在用户输入数学表达式后自动将其转换为二叉树。具体来说，表达式必须与上面的格式相同，一个有效的表达式可以递归定义如下:它必须是(X?Y)的形式，其中X和Y要么是数字，要么是有效表达式，并且?表示操作符(*，/，+，-) 来晚了，前段时间有点忙
看不懂你那个图片是怎么表示二叉树的
下面这个代码创建出了这颗树，你想要怎么输出就自己写代码吧
#!/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
# [, lchild, rchild]
last_token = None
ERROR = 256
NUM = 257
EOF = -1
def error(value):
return [, 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 ]:
return get_token()
if isdigit(ch):
ungetc(ch, stdin)
num = c_int()
libc.fscanf(stdin, b'%d', byref(num))
return [, None, None]
return [, None, None]
def unget_token(token):
global last_token
last_token = token
def factor():
token = get_token()
if token == NUM: return token
if token == ord('-'):
token = factor()
if token == ERROR: return token
return token
if token != ord('('): return error(token)
token = expression()
if token == ERROR: return token
temp = token
token = get_token()
if token != ord(')'): return error(token)
return temp
def term():
token = factor()
if token == ERROR: return token
a = token
token = get_token()
if token != ord('*') and token != ord('/'):
unget_token(token)
return a
op = token
token = term()
if token == ERROR: return token
b = token
op = a
op = b
return op
def expression():
token = term()
if token == ERROR: return token
a = token
token = get_token()
if token != ord('+') and token != ord('-'):
unget_token(token)
return a
op = token
token = expression()
if token == ERROR: return token
b = token
op = a
op = b
return op
def do_error():
print('错误的表达式!', file = sys.stderr)
while True:
token = get_token()
if token == ord('\n'): break
def val(tree):
if tree == NUM: return tree
if tree == ord('+'): return val(tree) + val(tree)
if tree == ord('*'): return val(tree) * val(tree)
if tree == ord('/'): return val(tree) / val(tree)
if tree == ord('-'):
return -val(tree) if tree == None else val(tree) - val(tree)
raise "未知的运算符!"
def line():
token = get_token()
if token == ord('\n'): return
unget_token(token)
token = expression()
if token == ERROR:
do_error()
return
result = token
token = get_token()
if token == ord('\n'):
#print(result)
print('>>> ' + str(val(result)))
return
do_error()
def lines():
token = get_token()
unget_token(token)
if token == EOF:
return
line()
lines()
return
def start():
lines()
token = get_token()
if token == 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. 调试，其实应该是边写代码边调试，写一点调试一点
页:
[1]