鱼C论坛

 找回密码
 立即注册
查看: 2463|回复: 8

[已解决]问一道递归的题!告诉我思路就好!

[复制链接]
发表于 2022-6-26 11:46:46 | 显示全部楼层 |阅读模式
25鱼币
其实是一道题的两个问题,写一个递归函数
1.input一个“表达式”,计算出他的结果。
2.input一个字符串,判断他是不是“表达式”,如果是则返回0,如果不是则返回第一个错误/多余的字符的位置。
表达式的定义是:<小括号(> <数字> <加减乘(+-*)><数字><小括号)>
例子:(1+(2*2)是表达式,(((2*1)+1)-1)也是。

我想了两个小时也没什么思路555
告诉我思路就好,感激不尽!!!
最佳答案
2022-6-26 11:46:47
1. 你没有说要使用的编程语言,而且把问题发在了 新手乐园 版块
所以我不知道你要求用哪个语言写,看你的问题中出现了 input 这个单词,初步判断是用python
2. python中的这个input函数每一次都会得到一行输入,但是我需要一次得到一个字符,而且有时候还需要把这个字符退回去,用input函数就需要自己写一个字符一个字符读取和退回字符的代码,C语言中有fgetc和ungetc函数,这两个函数就是我想要的,这里就直接调用C语言的这两个函数
3. 我干脆帮你把这两个要求合并一下吧,毕竟两个要求有太多相同的地方
合并成这样
输入一个字符串,如果是“表达式”,那就计算结果然后输出,如果不是“表达式”,那就报告错误
#!/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, rows, cols], lchild, rchild]
last_token = None
file_rows = 1
file_cols = 1

ERROR = 256
NUM = 257
EOF = -1

def error(value):
    return [[ERROR, value[1], value[2], value[3]], 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
    global file_cols, file_rows
    last_position = [file_rows, file_cols]
    ch = fgetc(stdin)
    file_cols += 1
    if ch in [ord(i) for i in [' ', '\t', '\v', '\f']]:
        return get_token()
    if isdigit(ch):
        ungetc(ch, stdin)
        file_cols -= 1
        num = c_int()
        libc.fscanf(stdin, b'%d', byref(num))
        file_cols += len(str(num.value))
        return [[NUM, num.value, *last_position], None, None]
    if ch == ord('\n'):
        file_rows += 1
        file_cols = 1
    return [[ch, ch, *last_position], 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])
    token = expression()
    if token[0][0] == ERROR: return token
    temp = token
    token = get_token()
    if token[0][0] != ord(')'): return error(token[0])
    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(info):
    print('错误的表达式!', file = sys.stderr)
    print(f'(\'{chr(info[1])}\',{info[2],info[3]})', 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(token[0])
        return
    result = token
    token = get_token()
    if token[0][0] == ord('\n'):
        #print(result)
        print('>>> ' + str(val(result)))
        return
    do_error(token[0])

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())

参考: https://fishc.com.cn/thread-213764-1-1.html

最佳答案

查看完整内容

1. 你没有说要使用的编程语言,而且把问题发在了 新手乐园 版块 所以我不知道你要求用哪个语言写,看你的问题中出现了 input 这个单词,初步判断是用python 2. python中的这个input函数每一次都会得到一行输入,但是我需要一次得到一个字符,而且有时候还需要把这个字符退回去,用input函数就需要自己写一个字符一个字符读取和退回字符的代码,C语言中有fgetc和ungetc函数,这两个函数就是我想要的,这里就直接调用C语言的这两个 ...
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-6-26 11:46:47 | 显示全部楼层    本楼为最佳答案   
1. 你没有说要使用的编程语言,而且把问题发在了 新手乐园 版块
所以我不知道你要求用哪个语言写,看你的问题中出现了 input 这个单词,初步判断是用python
2. python中的这个input函数每一次都会得到一行输入,但是我需要一次得到一个字符,而且有时候还需要把这个字符退回去,用input函数就需要自己写一个字符一个字符读取和退回字符的代码,C语言中有fgetc和ungetc函数,这两个函数就是我想要的,这里就直接调用C语言的这两个函数
3. 我干脆帮你把这两个要求合并一下吧,毕竟两个要求有太多相同的地方
合并成这样
输入一个字符串,如果是“表达式”,那就计算结果然后输出,如果不是“表达式”,那就报告错误
#!/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, rows, cols], lchild, rchild]
last_token = None
file_rows = 1
file_cols = 1

ERROR = 256
NUM = 257
EOF = -1

def error(value):
    return [[ERROR, value[1], value[2], value[3]], 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
    global file_cols, file_rows
    last_position = [file_rows, file_cols]
    ch = fgetc(stdin)
    file_cols += 1
    if ch in [ord(i) for i in [' ', '\t', '\v', '\f']]:
        return get_token()
    if isdigit(ch):
        ungetc(ch, stdin)
        file_cols -= 1
        num = c_int()
        libc.fscanf(stdin, b'%d', byref(num))
        file_cols += len(str(num.value))
        return [[NUM, num.value, *last_position], None, None]
    if ch == ord('\n'):
        file_rows += 1
        file_cols = 1
    return [[ch, ch, *last_position], 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])
    token = expression()
    if token[0][0] == ERROR: return token
    temp = token
    token = get_token()
    if token[0][0] != ord(')'): return error(token[0])
    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(info):
    print('错误的表达式!', file = sys.stderr)
    print(f'(\'{chr(info[1])}\',{info[2],info[3]})', 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(token[0])
        return
    result = token
    token = get_token()
    if token[0][0] == ord('\n'):
        #print(result)
        print('>>> ' + str(val(result)))
        return
    do_error(token[0])

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())

参考: https://fishc.com.cn/thread-213764-1-1.html
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-6-26 13:06:17 From FishC Mobile | 显示全部楼层
这东西不是用栈吗
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-6-26 13:07:14 | 显示全部楼层
用栈机制来处理括号 小甲鱼有专门讲这个的视频
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-6-26 13:22:18 | 显示全部楼层
排程場演算法(或调度场算法)和逆波兰表示法
https://fishc.com.cn/thread-212875-1-1.html
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-6-26 14:40:44 | 显示全部楼层
中缀改成后缀(逆波兰)表达式,如果表达式合法再计算
用栈实现
具体见小甲鱼的数据结构和算法篇——栈和队列
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-6-26 15:51:01 | 显示全部楼层
改一下
print(f'(\'{chr(info[1])}\',{info[2],info[3]})', file = sys.stderr)
print(f'(\'{chr(info[1])}\', {info[2],info[3]})', file = sys.stderr)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2022-6-27 00:02:33 | 显示全部楼层
感谢楼上的各位老哥,我这就去看视频。最佳答案给帮忙写了代码的老哥啦(虽然其实我用的是c++哈哈哈,不过还是很感谢您!)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-6-27 21:23:41 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-12-26 21:27

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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