首页 > 试题广场 >

牛牛与后缀表达式

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

【名词解释】
{\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

说明

算法知识视频讲解
添加回答
Java
空白01头像 空白01
//把字符串分开成单个字符，创建一个可变字符串和栈，是数字则追加进可变字符串，读入#则把可变字符串进栈同时清空可变字符串，读到运算符则出栈2个数进行运算，把结果重新入栈
import java.util.*;

public class Solution {
    /**
     * 给定一个后缀表达式，返回它的结果
     * @param str string字符串
     * @return long长整型
     */
    public long legalExp (String str) {
        Stack<Long> Sta = new Stack<>();
        String[] s = str.split("");
        StringBuffer p =  new StringBuffer();
        for (int i = 0; i < s.length; i++) {
            String token = s[i];
            if (token.isEmpty()) {
                return -1;
            }

            // 处理运算符
            if (token.equals("+") || token.equals("-") || token.equals("*")) {        if (Sta.size() < 2) {
                        return -10; // 操作数不足，非法表达式
                }
                long num2 = Sta.pop();
                long num1 = Sta.pop();
                if (token.equals("+")) {
                    Sta.add(num1 + num2);
                } else if (token.equals("-")) {
                    Sta.add(num1 - num2); // 减法顺序正确
                } else if (token.equals("*")) {
                    Sta.add(num1 * num2); // 乘法顺序不影响，统一写法
                }
            } else if (token.equals("#")) {
                try {
                    Sta.add((long)Integer.parseInt(p.toString()));
                    p.delete(0, p.length());

                } catch (NumberFormatException e) {
                    return -11;
                }
                   
               
            }else {//是数字
                p.append(s[i]);
            }
           
        }
        if (Sta.size() != 1) {
            return -2;
        }

        return (long) Sta.pop();
    }
}
发表于 2026-02-26 15:31:58 回复(0)
Java
爱敲代码的小豪头像 爱敲代码的小豪 
import java.util.*;

public class Solution {
    public long legalExp (String str) {
        Deque<Long> stack = new ArrayDeque<>();
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            if ('0'<=str.charAt(i)&&str.charAt(i)<='9') {
                s.append(str.charAt(i));
                continue;
            } else if (str.charAt(i) == '#') {
                long n = Long.parseLong(s.toString());
                s.delete(0,s.length());
                stack.push(n);
            } else {
                long a = stack.pop(),b = stack.pop();
                if (str.charAt(i) == '+') {
                    stack.push(a+b);
                } else if (str.charAt(i) == '-') {
                    stack.push(b-a);
                }else{
                    stack.push(a*b);
                }
            }
        }
        return stack.pop();
    }
}
发表于 2026-02-02 23:59:44 回复(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)
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)
提交观点

问题信息

字符串
难度：
6条回答 6747浏览

热门推荐

通过挑战的用户

查看代码

相关试题

牛牛与后缀表达式

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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