鱼C论坛

 找回密码
 立即注册
查看: 1366|回复: 1

[已解决]求救!!!!谢谢大家

[复制链接]
发表于 2022-5-23 22:16:40 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
设计一个python程序,它可以在用户输入数学表达式后自动将其转换为二叉树。具体来说,表达式必须与上面的格式相同,一个有效的表达式可以递归定义如下:
          它必须是(X?Y)的形式,其中X和Y要么是数字,要么是有效表达式,并且?表示操作符(*,/,+,-)
最佳答案
2022-6-3 14:46:20
来晚了,前段时间有点忙

看不懂你那个图片是怎么表示二叉树的
下面这个代码创建出了这颗树,你想要怎么输出就自己写代码吧

  1. #!/usr/bin/env python
  2. #coding=utf-8

  3. from ctypes import cdll
  4. from ctypes.util import find_library
  5. from ctypes import c_void_p, c_int, byref
  6. import sys

  7. libc = cdll.LoadLibrary(find_library('c'))
  8. stdin = c_void_p.in_dll(libc, 'stdin')

  9. def fgetc(stream):
  10.     return libc.fgetc(stream)

  11. def ungetc(ch, stream):
  12.     return libc.ungetc(ch, stream)

  13. # token
  14. # [[symbol, value], lchild, rchild]
  15. last_token = None

  16. ERROR = 256
  17. NUM = 257
  18. EOF = -1

  19. def error(value):
  20.     return [[ERROR, value], None, None]

  21. def isdigit(ch):
  22.     return ch >= ord('0') and ch <= ord('9')

  23. def get_token():
  24.     global last_token
  25.     if last_token:
  26.         result = last_token
  27.         last_token = None
  28.         return result
  29.     ch = fgetc(stdin)
  30.     if ch in [ord(i) for i in [' ', '\t', '\v', '\f']]:
  31.         return get_token()
  32.     if isdigit(ch):
  33.         ungetc(ch, stdin)
  34.         num = c_int()
  35.         libc.fscanf(stdin, b'%d', byref(num))
  36.         return [[NUM, num.value], None, None]
  37.     return [[ch, None], None, None]

  38. def unget_token(token):
  39.     global last_token
  40.     last_token = token

  41. def factor():
  42.     token = get_token()
  43.     if token[0][0] == NUM: return token
  44.     if token[0][0] == ord('-'):
  45.         token[1] = factor()
  46.         if token[1][0][0] == ERROR: return token[1]
  47.         return token
  48.     if token[0][0] != ord('('): return error(token[0][1])
  49.     token = expression()
  50.     if token[0][0] == ERROR: return token
  51.     temp = token
  52.     token = get_token()
  53.     if token[0][0] != ord(')'): return error(token[0][1])
  54.     return temp

  55. def term():
  56.     token = factor()
  57.     if token[0][0] == ERROR: return token
  58.     a = token
  59.     token = get_token()
  60.     if token[0][0] != ord('*') and token[0][0] != ord('/'):
  61.         unget_token(token)
  62.         return a
  63.     op = token
  64.     token = term()
  65.     if token[0][0] == ERROR: return token
  66.     b = token
  67.     op[1] = a
  68.     op[2] = b
  69.     return op

  70. def expression():
  71.     token = term()
  72.     if token[0][0] == ERROR: return token
  73.     a = token
  74.     token = get_token()
  75.     if token[0][0] != ord('+') and token[0][0] != ord('-'):
  76.         unget_token(token)
  77.         return a
  78.     op = token
  79.     token = expression()
  80.     if token[0][0] == ERROR: return token
  81.     b = token
  82.     op[1] = a
  83.     op[2] = b
  84.     return op

  85. def do_error():
  86.     print('错误的表达式!', file = sys.stderr)
  87.     while True:
  88.         token = get_token()
  89.         if token[0][0] == ord('\n'): break

  90. def val(tree):
  91.     if tree[0][0] == NUM: return tree[0][1]
  92.     if tree[0][0] == ord('+'): return val(tree[1]) + val(tree[2])
  93.     if tree[0][0] == ord('*'): return val(tree[1]) * val(tree[2])
  94.     if tree[0][0] == ord('/'): return val(tree[1]) / val(tree[2])
  95.     if tree[0][0] == ord('-'):
  96.         return -val(tree[1]) if tree[2] == None else val(tree[1]) - val(tree[2])
  97.     raise "未知的运算符!"

  98. def line():
  99.     token = get_token()
  100.     if token[0][0] == ord('\n'): return
  101.     unget_token(token)
  102.     token = expression()
  103.     if token[0][0] == ERROR:
  104.         do_error()
  105.         return
  106.     result = token
  107.     token = get_token()
  108.     if token[0][0] == ord('\n'):
  109.         #print(result)
  110.         print('>>> ' + str(val(result)))
  111.         return
  112.     do_error()

  113. def lines():
  114.     token = get_token()
  115.     unget_token(token)
  116.     if token[0][0] == EOF:
  117.         return
  118.     line()
  119.     lines()
  120.     return

  121. def start():
  122.     lines()
  123.     token = get_token()
  124.     if token[0][0] == EOF: return True
  125.     return False

  126. print(start())
复制代码


下面说一下这个代码的思路
1. 先写出这个语言(表达式)的文法
  1. start: lines (EOF);

  2. lines: (EMPTY)
  3.      | line lines
  4.      ;

  5. line: expression '\n' {print(expression);}
  6.     | '\n'
  7.     | (ERROR) {printf("错误的表达式!\n");}
  8.     ;

  9. expression: term
  10.           | expression '+' term {$$ = $1 + $3;}
  11.           | expression '-' term {$$ = $1 - $3;}
  12.           ;

  13. term: factor
  14.     | term '*' factor {$$ = $1 * $3;}
  15.     | term '/' factor {$$ = $1 / $3;}
  16.     ;

  17. factor: NUM
  18.       | '-' factor {$$ = -$2;}
  19.       | '(' expression ')' {$$ = $2;}
  20.       ;
复制代码

2. 用递归下降分析,照着这个文法写代码
3. 调试,其实应该是边写代码边调试,写一点调试一点
微信图片_20220523221327.png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-6-3 14:46:20 | 显示全部楼层    本楼为最佳答案   
来晚了,前段时间有点忙

看不懂你那个图片是怎么表示二叉树的
下面这个代码创建出了这颗树,你想要怎么输出就自己写代码吧

  1. #!/usr/bin/env python
  2. #coding=utf-8

  3. from ctypes import cdll
  4. from ctypes.util import find_library
  5. from ctypes import c_void_p, c_int, byref
  6. import sys

  7. libc = cdll.LoadLibrary(find_library('c'))
  8. stdin = c_void_p.in_dll(libc, 'stdin')

  9. def fgetc(stream):
  10.     return libc.fgetc(stream)

  11. def ungetc(ch, stream):
  12.     return libc.ungetc(ch, stream)

  13. # token
  14. # [[symbol, value], lchild, rchild]
  15. last_token = None

  16. ERROR = 256
  17. NUM = 257
  18. EOF = -1

  19. def error(value):
  20.     return [[ERROR, value], None, None]

  21. def isdigit(ch):
  22.     return ch >= ord('0') and ch <= ord('9')

  23. def get_token():
  24.     global last_token
  25.     if last_token:
  26.         result = last_token
  27.         last_token = None
  28.         return result
  29.     ch = fgetc(stdin)
  30.     if ch in [ord(i) for i in [' ', '\t', '\v', '\f']]:
  31.         return get_token()
  32.     if isdigit(ch):
  33.         ungetc(ch, stdin)
  34.         num = c_int()
  35.         libc.fscanf(stdin, b'%d', byref(num))
  36.         return [[NUM, num.value], None, None]
  37.     return [[ch, None], None, None]

  38. def unget_token(token):
  39.     global last_token
  40.     last_token = token

  41. def factor():
  42.     token = get_token()
  43.     if token[0][0] == NUM: return token
  44.     if token[0][0] == ord('-'):
  45.         token[1] = factor()
  46.         if token[1][0][0] == ERROR: return token[1]
  47.         return token
  48.     if token[0][0] != ord('('): return error(token[0][1])
  49.     token = expression()
  50.     if token[0][0] == ERROR: return token
  51.     temp = token
  52.     token = get_token()
  53.     if token[0][0] != ord(')'): return error(token[0][1])
  54.     return temp

  55. def term():
  56.     token = factor()
  57.     if token[0][0] == ERROR: return token
  58.     a = token
  59.     token = get_token()
  60.     if token[0][0] != ord('*') and token[0][0] != ord('/'):
  61.         unget_token(token)
  62.         return a
  63.     op = token
  64.     token = term()
  65.     if token[0][0] == ERROR: return token
  66.     b = token
  67.     op[1] = a
  68.     op[2] = b
  69.     return op

  70. def expression():
  71.     token = term()
  72.     if token[0][0] == ERROR: return token
  73.     a = token
  74.     token = get_token()
  75.     if token[0][0] != ord('+') and token[0][0] != ord('-'):
  76.         unget_token(token)
  77.         return a
  78.     op = token
  79.     token = expression()
  80.     if token[0][0] == ERROR: return token
  81.     b = token
  82.     op[1] = a
  83.     op[2] = b
  84.     return op

  85. def do_error():
  86.     print('错误的表达式!', file = sys.stderr)
  87.     while True:
  88.         token = get_token()
  89.         if token[0][0] == ord('\n'): break

  90. def val(tree):
  91.     if tree[0][0] == NUM: return tree[0][1]
  92.     if tree[0][0] == ord('+'): return val(tree[1]) + val(tree[2])
  93.     if tree[0][0] == ord('*'): return val(tree[1]) * val(tree[2])
  94.     if tree[0][0] == ord('/'): return val(tree[1]) / val(tree[2])
  95.     if tree[0][0] == ord('-'):
  96.         return -val(tree[1]) if tree[2] == None else val(tree[1]) - val(tree[2])
  97.     raise "未知的运算符!"

  98. def line():
  99.     token = get_token()
  100.     if token[0][0] == ord('\n'): return
  101.     unget_token(token)
  102.     token = expression()
  103.     if token[0][0] == ERROR:
  104.         do_error()
  105.         return
  106.     result = token
  107.     token = get_token()
  108.     if token[0][0] == ord('\n'):
  109.         #print(result)
  110.         print('>>> ' + str(val(result)))
  111.         return
  112.     do_error()

  113. def lines():
  114.     token = get_token()
  115.     unget_token(token)
  116.     if token[0][0] == EOF:
  117.         return
  118.     line()
  119.     lines()
  120.     return

  121. def start():
  122.     lines()
  123.     token = get_token()
  124.     if token[0][0] == EOF: return True
  125.     return False

  126. print(start())
复制代码


下面说一下这个代码的思路
1. 先写出这个语言(表达式)的文法
  1. start: lines (EOF);

  2. lines: (EMPTY)
  3.      | line lines
  4.      ;

  5. line: expression '\n' {print(expression);}
  6.     | '\n'
  7.     | (ERROR) {printf("错误的表达式!\n");}
  8.     ;

  9. expression: term
  10.           | expression '+' term {$$ = $1 + $3;}
  11.           | expression '-' term {$$ = $1 - $3;}
  12.           ;

  13. term: factor
  14.     | term '*' factor {$$ = $1 * $3;}
  15.     | term '/' factor {$$ = $1 / $3;}
  16.     ;

  17. factor: NUM
  18.       | '-' factor {$$ = -$2;}
  19.       | '(' expression ')' {$$ = $2;}
  20.       ;
复制代码

2. 用递归下降分析,照着这个文法写代码
3. 调试,其实应该是边写代码边调试,写一点调试一点
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 21:41

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表