[已解决]表达式求值问题

yangzhixiaohuli

在一个表达式中，只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”，请求出表达式的值。(“/”用整数除法)。

输入格式:
共1 行，为一个算式。 （算式长度<=30 其中所有数据在 0~2^31-1的范围内）。

输出格式:
共一行，为表达式的值。

输入样例:
在这里给出一组输入。例如：

1+(3+2)*(7^2+6*9)/(2)
输出样例:
在这里给出相应的输出。例如：

258

这题用C或者C++怎么做

最佳答案

月排行榜 / 总排行榜

FishC

2024-11-1 17:58:32

要解决这个表达式求值问题，可以使用“逆波兰表达式”（RPN）或“中缀表达式转后缀表达式”的方法。以下是一个简单的思路：

1. **将中缀表达式转换为后缀表达式**：使用栈来处理运算符的优先级和括号。
2. **计算后缀表达式的值**：再次使用栈来计算后缀表达式的结果。

以下是实现这个过程的Python代码：

def precedence(op):
    if op == '+' or op == '-':
        return 1
    if op == '*' or op == '/':
        return 2
    if op == '^':
        return 3
    return 0

def apply_op(a, b, op):
    if op == '+': return a + b
    if op == '-': return a - b
    if op == '*': return a * b
    if op == '/': return a // b
    if op == '^': return a ** b

def evaluate(expression):
    values = []
    ops = []
    i = 0
    while i < len(expression):
        if expression[i] == ' ':
            i += 1
            continue
        elif expression[i] == '(':
            ops.append(expression[i])
        elif expression[i].isdigit():
            val = 0
            while i < len(expression) and expression[i].isdigit():
                val = (val * 10) + int(expression[i])
                i += 1
            values.append(val)
            i -= 1
        elif expression[i] == ')':
            while len(ops) != 0 and ops[-1] != '(':
                val2 = values.pop()
                val1 = values.pop()
                op = ops.pop()
                values.append(apply_op(val1, val2, op))
            ops.pop()
        else:
            while (len(ops) != 0 and precedence(ops[-1]) >= precedence(expression[i])):
                val2 = values.pop()
                val1 = values.pop()
                op = ops.pop()
                values.append(apply_op(val1, val2, op))
            ops.append(expression[i])
        i += 1

    while len(ops) != 0:
        val2 = values.pop()
        val1 = values.pop()
        op = ops.pop()
        values.append(apply_op(val1, val2, op))

    return values[-1]

# 示例
expression = "3 + 5 * (2 - 8)"
result = evaluate(expression)
print(result)

这个代码会计算给定的算术表达式，并返回其结果。请注意，代码中使用了整数除法（`//`），以符合题目要求。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

要解决这个表达式求值问题，可以使用“逆波兰表达式”（RPN）或“中缀表达式转后缀表达式”的方法。以下是一个简单的思路：

1. **将中缀表达式转换为后缀表达式**：使用栈来处理运算符的优先级和括号。
2. **计算后缀表达式的值**：再次使用栈来计算后缀表达式的结果。

以下是实现这个过程的Python代码：

def precedence(op):
    if op == '+' or op == '-':
        return 1
    if op == '*' or op == '/':
        return 2
    if op == '^':
        return 3
    return 0

def apply_op(a, b, op):
    if op == '+': return a + b
    if op == '-': return a - b
    if op == '*': return a * b
    if op == '/': return a // b
    if op == '^': return a ** b

def evaluate(expression):
    values = []
    ops = []
    i = 0
    while i < len(expression):
        if expression[i] == ' ':
            i += 1
            continue
        elif expression[i] == '(':
            ops.append(expression[i])
        elif expression[i].isdigit():
            val = 0
            while i < len(expression) and expression[i].isdigit():
                val = (val * 10) + int(expression[i])
                i += 1
            values.append(val)
            i -= 1
        elif expression[i] == ')':
            while len(ops) != 0 and ops[-1] != '(':
                val2 = values.pop()
                val1 = values.pop()
                op = ops.pop()
                values.append(apply_op(val1, val2, op))
            ops.pop()
        else:
            while (len(ops) != 0 and precedence(ops[-1]) >= precedence(expression[i])):
                val2 = values.pop()
                val1 = values.pop()
                op = ops.pop()
                values.append(apply_op(val1, val2, op))
            ops.append(expression[i])
        i += 1

    while len(ops) != 0:
        val2 = values.pop()
        val1 = values.pop()
        op = ops.pop()
        values.append(apply_op(val1, val2, op))

    return values[-1]

# 示例
expression = "3 + 5 * (2 - 8)"
result = evaluate(expression)
print(result)

这个代码会计算给定的算术表达式，并返回其结果。请注意，代码中使用了整数除法（`//`），以符合题目要求。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。