首页 > 试题广场 >

牛牛与后缀表达式

[编程题]牛牛与后缀表达式
  • 热度指数：3564 时间限制：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 中只含有 ‘+’、’-‘、’*‘三种运算，分别表示加法、减法和乘法，且任意计算过程和计算结果的绝对值一定不会超过 。

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

输入

"1#1#+"

输出

2

说明

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

输入

"12#3#+15#*"

输出

225

说明

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

输入

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

输出

4

说明

算法知识视频讲解
添加回答
C
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
#include <errno.h>

// #define OK 1
// #define ERROR -1
// #define MEMORY_OVERFLOW -2

typedef enum { OK = 1, ERROR = -1, MEMORY_OVERFLOW = -2 } Status;

#define NOT !

#define DEFAULT_CAPACITY 8
#define InitStack(S) __InitStack(S, DEFAULT_CAPACITY)

typedef long long LL;

// ==================== 顺序栈存储结构表示与实现 ====================
typedef LL SElemType;

typedef struct {
  SElemType* base;
  SElemType* top;
  size_t capacity;
} SqStack;

Status __InitStack(SqStack* S, int initialCapacity) {
  if (initialCapacity < 1) {
    fprintf(stderr, 
            "__InitStack ERROR: The initialCapacity %d Must be > 0!",
            initialCapacity);
    return ERROR;
  }
  
  if (!((*S).base = (SElemType*) malloc(initialCapacity * sizeof(SElemType)))) {
    fprintf(stderr,
            "__InitStack Memory Overflow: %s\n",
            strerror(errno));
    exit(MEMORY_OVERFLOW);
  }
  
  (*S).top = (*S).base;
  (*S).capacity = initialCapacity;
  return OK;
}

int StackEmpty(SqStack* S) {
  return (*S).top == (*S).base;
}

int StackFull(SqStack* S) {
  return (*S).top - (*S).base == (*S).capacity; 
}

size_t StackLength(SqStack* S) {
  return (*S).top - (*S).base;
}

void __large_capacity(SqStack* S) {
  if (!((*S).base = (SElemType*) 
        realloc((*S).base, ((*S).capacity << 1) * sizeof(SElemType)))) {
    
    fprintf(stderr,
            "__large_capacity Memory Overflow: %s\n",
            strerror(errno));
    exit(MEMORY_OVERFLOW);
  }
  
  (*S).top = (*S).base + (*S).capacity;
  (*S).capacity <<= 1;
}

Status Push(SqStack* S, SElemType e) {
  if (StackFull(S))
    __large_capacity(S);
  
  *(*S).top++ = e;
  return OK;
}

Status Pop(SqStack* S, SElemType* e) {
  if (StackEmpty(S)) {
    fputs("Pop ERROR: The stack is empty!\n", stderr);
    return ERROR;
  }
  *e = *--(*S).top;
  return OK;
}

Status DestroyStack(SqStack* S) {
  free((*S).base);
  (*S).top = NULL;
  return OK;
}
// ==================== 顺序栈存储结构表示与实现 ====================


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 给定一个后缀表达式，返回它的结果
 * @param str string字符串 
 * @return long长整型
 */
long long legalExp(char* str) {
  
  SqStack S;
  InitStack(&S);
  
  LL num = 0, n1, n2;
  while (*str) {
    switch (*str) {
      case '+':
        Pop(&S, &n2); Pop(&S, &n1);
        Push(&S, n1 + n2);
        break;
      case '-':
        Pop(&S, &n2); Pop(&S, &n1);
        Push(&S, n1 - n2);
        break;
      case '*':
        Pop(&S, &n2); Pop(&S, &n1);
        Push(&S, n1 * n2);
        break;
      case '#':
        Push(&S, num);
        num = 0;
        break;
      default: // numerical
        num = num * 10 + *str - 48;
        break;
    }
    ++str;
  }
  
  LL ans;
  Pop(&S, &ans);
  
  DestroyStack(&S);
  return ans;
}

发表于 2021-07-16 20:01:51 回复(0)
baneling头像 baneling
可能比较简洁的版本 
long long legalExp(string str) {
	stack<long long> operand;
	long long a=0;
	for(int i=0;i<str.length();i++) {
		if(str[i]>='0'&&str[i]<='9')
			a=a*10+str[i]-'0';
		switch(str[i]) {
			case '#' :
				if(str[i+1]>='0'&&str[i+1]<='9') {
					operand.push(a);
					a=0;
				}
				break;
			case '+': a=operand.top()+a; break;
			case '-': a=operand.top()-a; break;
			case '*': a=operand.top()*a; break;
			default: break;
		}
		if(str[i]=='+'||str[i]=='-'||str[i]=='*') {
			operand.pop();
			if(i+1<str.length()&&str[i+1]>='0'&&str[i+1]<='9') {
				operand.push(a);
				a=0;
			}
		}
	}
	return a;
}


发表于 2021-02-07 14:32:27 回复(0)
Java
BraveCoder头像 BraveCoder 
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定一个后缀表达式，返回它的结果
     * @param str string字符串
     * @return long长整型
     */
    public long legalExp (String str) {
        Stack<Long> stack = new Stack<>();
        StringBuilder numBuilder = new StringBuilder();

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);

            if (c == '#') {
                // 遇到结束符，将构建的数字入栈
                if (numBuilder.length() > 0) {
                    long num = Long.parseLong(numBuilder.toString());
                    stack.push(num);
                    numBuilder.setLength(0); // 重置用于下一个数字
                }
            } else if (c == '+' || c == '-' || c == '*') {
                // 遇到运算符，弹出两个操作数进行计算
                long b = stack.pop();
                long a = stack.pop();
                long result = 0;

                switch (c) {
                    case '+':
                        result = a + b;
                        break;
                    case '-':
                        result = a - b;
                        break;
                    case '*':
                        result = a * b;
                        break;
                }
                stack.push(result);
            } else {
                // 数字字符，继续构建数字（包括可能的负号）
                numBuilder.append(c);
            }
        }

        // 栈顶元素即为最终结果
        return stack.pop();
    }
}

发表于 2025-07-31 23:06:57 回复(0)
C++
Nitrene头像 Nitrene
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定一个后缀表达式，返回它的结果
     * @param str string字符串
     * @return long长整型
     */
    long long legalExp(string str) {
        // write code here
        long long d=0;
        int i=0;
        int n=str.length();
        stack<long long> st;
        while(i<n){
            long long x,y;
            if(str[i]<='9'&&str[i]>='0'){
                d=str[i]-(long long)'0'+d*10;
            }
            else if(str[i]=='#'){
                st.push(d);
                d=0;
                i++;
                continue;
            }
            else if(str[i]=='*'){
                y=st.top();
                st.pop();
                x=st.top();
                st.pop();
                st.push(x*y);
            }
            else if(str[i]=='/'){
                y=st.top();
                st.pop();
                x=st.top();
                st.pop();
                st.push(x/y);
            }
            else if(str[i]=='+'){
                y=st.top();
                st.pop();
                x=st.top();
                st.pop();
                st.push(x+y);
            }
            else if(str[i]=='-'){
                y=st.top();
                st.pop();
                x=st.top();
                st.pop();
                st.push(x-y);
            }
            i++;
        }
        return st.top();
    }
};
发表于 2025-09-23 10:18:25 回复(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)
Java
拒绝无效加班的柯基很想被叫靓仔头像 拒绝无效加班的柯基很想被叫靓仔

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定一个后缀表达式，返回它的结果
     * @param str string字符串
     * @return long长整型
     */
    public long legalExp (String str) {
        // write code here
        Deque<Character> ops = new ArrayDeque<>();
        Deque<Long> nums = new ArrayDeque<>();
        ops.push('#');
        for(int i = 0;i < str.length();i++){
            char c = str.charAt(i);
            if(c >= '0' && c <= '9'){//输入为数字，当输入字符是第一个字符或前一个字符是操作符时，将数字压入栈中，若后一位是数字，则转化为多位数入栈
                if(i == 0 || str.charAt(i - 1) == '#' || str.charAt(i - 1) == '+' || str.charAt(i - 1) == '-' || str.charAt(i - 1) == '*'){
                    nums.push((long) (c - '0'));//将char转化为int，再转化为long
                    System.out.println(nums.peek());
                    while (i + 1 < str.length() && str.charAt(i + 1) >= '0' && str.charAt(i + 1) <= '9'){
                        nums.push(nums.pop() * 10 + str.charAt(i + 1) - '0');
                        System.out.println(nums.peek());
                        i++;
                    }
                }
            }else{//输入为操作符，入栈，若栈顶为操作符，则计算
                if(c == '+' || c == '*' || c == '-'){ops.push(c);}
                while(ops.peek() == '-' || ops.peek() == '+' || ops.peek() == '*'){
                    long b = nums.pop();
                    long a = nums.pop();
                    char op = ops.pop();
                    switch(op){
                        case '*':
                            nums.push(a * b);
                            System.out.println(nums.peek());
                            break;
                        case '+':
                            nums.push(a + b);
                            System.out.println(nums.peek());
                            break;
                        case '-':
                            nums.push(a - b);
                            System.out.println(nums.peek());
                            break;
                        }
                    }
                }

            }
        return nums.peek();
    }
}
发表于 2025-07-11 15:43:24 回复(0)
Python3
GB279824头像 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)
孙新头像 孙新
这个也太简单了，是不是考验代码优不优美。用std::string，用find获取两个#位置，其他直接计算即可。
发表于 2021-01-22 18:50:32 回复(0)
提交观点

问题信息

字符串
难度：
8条回答 6158浏览

热门推荐

通过挑战的用户

查看代码

相关试题

牛牛与后缀表达式

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号