首页 > 试题广场 >

牛牛与后缀表达式

[编程题]牛牛与后缀表达式

热度指数：9362 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

${\hspace{15pt}}$ 给定牛牛一个后缀表达式 $s$ （ $1 \le |s| \le 10^6$ ），计算它的结果，例如， $1+1$ 对应的后缀表达式为 $\text{1#1#+}$ ，其中 $\text{#}$ 为参与运算的参数的结束标识符。

${\hspace{15pt}}$ 输入数据保证表达式 $s$ 一定合法， $s$ 中只含有 ‘+’、’-‘、’*‘三种运算，分别表示加法、减法和乘法，且任意计算过程和计算结果的绝对值一定不会超过 $10^{18}$ 。

【名词解释】

${\hspace{15pt}}$ 后缀表达式：一种数学表达式表示法，其中所有运算符都位于其操作数之后，并通过从左到右扫描表达式并使用栈进行操作数和结果的管理来确定明确的运算顺序，无需括号。

示例1

输入

"1#1#+"

输出

说明

1#1#+这个后缀表达式表示的式子是1+1，结果为2

示例2

输入

"12#3#+15#*"

输出

说明

12#3#+15#*这个后缀表达式表示的式子是(12+3)*15，结果为225

示例3

输入

"1#1#4#5#-*+1#4#*+"

输出

说明

算法知识视频讲解

Python3

吐你口水

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

# 给定一个后缀表达式，返回它的结果

# @param str string字符串

# @return long长整型

class Solution:

def legalExp(self , str ):

# write code here

lst = []

t = 0

for i in range(len(str)):

if str[i] == '#':

lst.append(int(str[t:i]))

t = i + 1

elif str[i] == '-':

a = lst[-1]

b = lst[-2]

lst.pop(-1)

lst.append(b - a)

t = i+1

elif str[i] == '+':

a = lst[-1]

b = lst[-2]

lst.pop(-1)

lst.append(b + a)

t = i + 1

elif str[i] == '*':

a = lst[-1]

b = lst[-2]

lst.pop(-1)

lst.append(b * a)

t = i + 1

return lst[0]

发表于 2026-01-31 10:37:09 回复(0)

Python3

只想搞钱的芝士很好奇

class Solution:

def legalExp(self , str ):

nums = []

num = ""

for ch in str:

if ch.isdigit():

num += ch

elif ch == '#':

nums.append(int(num))

num = ""

else:

if ch == '+':

nums[-2] = nums[-2] + nums[-1]

elif ch == '-':

nums[-2] = nums[-2] - nums[-1]

elif ch == '*':

nums[-2] = nums[-2] * nums[-1]

del nums[-1]

return nums[0]

发表于 2026-01-23 20:10:44 回复(0)

Python3

袁钦照

import re
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 给定一个后缀表达式，返回它的结果
# @param str string字符串 
# @return long长整型
#
class Solution:
    def legalExp(self , str ):
        # write code here
        s = re.findall(r'\d+|[+*#\-]', str)
        new_s = []
        list_s = []
        for j in s:
            if j == "#":
                continue
            else:
                new_s.append(j)
        res = 0
        for i in new_s:
            if i == "+":
                res = int(list_s[-2]) + int(list_s[-1])
                list_s[-2] = int(res)
                list_s.pop()
            elif i == "-":
                res = int(list_s[-2]) - int(list_s[-1])
                list_s[-2] = int(res)
                list_s.pop()
            elif i == "*":
                res = int(list_s[-2]) * int(list_s[-1])
                list_s[-2] = int(res)
                list_s.pop()
            else:
                list_s.append(i)
        return res

发表于 2025-11-20 11:09:19 回复(0)

Python3

意若久时天然呆

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

# 给定一个后缀表达式，返回它的结果

# @param str string字符串

# @return long长整型

class Solution:

def legalExp(self, str):

# write code here

s, t = "", []

for i in str:

if i.isdigit():

s += i

elif i == "#":

t.append(int(s))

s = ""

elif i in ["+", "-", "*"]:

n2, n1 = t.pop(), t.pop()

if i == "+":

t.append(n1 + n2)

elif i == "-":

t.append(n1 - n2)

elif i == "*":

t.append(n1 * n2)

return t[-1]

发表于 2025-11-19 17:47:37 回复(0)

Python3

新生力量

class Solution:

def legalExp(self, str):

# write code here

stack = []

# 初始化一个空字符串用于构建多位数

num_str = ""

for char in str:

if char.isdigit(): # 如果字符是数字

num_str += char # 将其添加到num_str中

elif char in ["+", "-", "*"]: # 如果字符是运算符

# 弹出两个操作数

num2 = stack.pop()

num1 = stack.pop()

# 根据运算符进行计算

if char == "+":

stack.append(num1 + num2)

elif char == "-":

stack.append(num1 - num2)

elif char == "*":

stack.append(num1 * num2)

elif char == "#": # 如果字符是'#'，表示一个数字的结束

stack.append(int(num_str)) # 将构建的多位数转换为整数并压入栈

num_str = "" # 重置num_str为空字符串，用于构建下一个数字

# 栈顶元素即为结果

return stack[0]

发表于 2025-09-17 05:01:15 回复(0)

Python3

GB279824

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 给定一个后缀表达式，返回它的结果
# @param str string字符串 
# @return long长整型
#
class Solution:
    def legalExp(self , str ):
        # write code here
        def apply_op(a,b,op):
            if op == "+":return a+b
            if op == "-":return a-b
            if op == "*":return a*b
        
        stack = []
        i = 0
        while i < len(str):
            if str[i].isdigit():
                num = 0
                while i < len(str) and str[i].isdigit():
                    num = num *10 + int(str[i])
                    i += 1
                stack.append(num)
            elif str[i] == "#":
                i += 1
            elif str[i] in ("+","-","*"):
                num1 = stack.pop()
                num2 = stack.pop()
                op = str[i]
                stack.append(apply_op(num2,num1,op))
                i += 1
        return int(stack[0])  

if __name__ == "__main__":
    s = str(input().strip().replace('"',''))
    print(Solution().legalExp(s))

发表于 2025-06-10 20:28:11 回复(0)

提交观点

问题信息

字符串

难度：

10条回答 127收藏 6746浏览

通过挑战的用户

查看代码

Duoni

2022-12-03 19:50:26
牛客94970...

2022-02-18 13:56:36
MaKuRo_123

2022-02-10 14:36:26
青椒炒牛肉

2021-11-21 22:54:57
牛客22557...

2021-10-14 22:34:52

牛牛与后缀表达式

输入

输出

说明

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题