华宇信息笔试 - 1016

简单的字符串压缩

题面

对输入的文本字符串进行简单的压缩，输出压缩后的字符串。

输入描述：
输入为一个简单的文本字符串，里面只包含 $26$ 个大小写英文字符，字符可重复，比如 "aaabbbcccddd"。

输出描述：
将相同的字符进行压缩，计算相同字符的个数，然后得到压缩结果，比如 "aaabbbcccddd" 压缩后的结果为 "a3b3c3d3"，最后输出结果就为 "a3b3c3d3"。

示例

输入：aaabbbcccddd

输出：a3b3c3d3

思路与代码：

遍历一次字符串，通过维护一个计数器来跟踪当前连续字符的数量，当字符变化时更新计数器结果。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int n = s.length();

        if (s == null || n == 0) {
            System.out.println("");
            return;
        }

        StringBuilder res = new StringBuilder();
        int cnt = 1;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                cnt++;
            } else {
                res.append(s.charAt(i - 1));
                res.append(cnt);
                cnt = 1;
            }
        }
        
        // 加上剩余的字符
        res.append(s.charAt(n - 1));
        res.append(cnt);
        
        System.out.println(res.toString());
    }
}

简单的数学表达式计算

题面

输入为一个简单的数学表达式字符串，字符串只包含若干一位的正整数和若干计算符号，计算符号只有 "+"、"-"、"*" 三种，求该表达式的计算结果。计算结果范围为 $-2^{63}$ 至 $2^{63}$ 之间。

输入描述：
输入为简单的数学表达式字符串，字符串只包含若干一位的正整数和若干计算符号，计算符号只有 "+"、-、"*" 三种。例如 "$1+2+34-56$"、"$22-33+44$"、"$9-8-76+5+43$" 等。

输出描述：
输出为输入数学表达式计算结果，计算结果范围为 $-2^{63}$ 至 $2^{63}$ 之间。比如输入为 "$1+2+34-56$" 时，输出为 "$-15$"。输入为 "$22-33+4*4$" 时，输出为 "$11$"。

示例

输入：1+2-34+56
输出：21

思路与代码：

类似于逆波兰表达式的计算，使用两个栈分别存数字和符号来实现。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int n = s.length();

        Stack<Long> nums = new Stack<>();
        Stack<Character> op = new Stack<>();
        int i = 0;
        while (i < n){
            char c = s.charAt(i);
            if (Character.isDigit(c)){
                long num = s.charAt(i) - '0';
                nums.push(num);
                i++;
                continue;
            }

            /* 多位数字的写法：
            if (Character.isDigit(c)) {
                long num = 0;
                while (i < n && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                nums.push(num);
                continue;
            }
            */

            while (!op.isEmpty() && check(op.peek()) >= check(c)){
                long b = nums.pop();
                long a = nums.pop();
                nums.push(fun(op.pop(), a, b));
            }

            op.push(c);
            i++;
        }

        while (!op.isEmpty()){
            long b = nums.pop();
            long a = nums.pop();
            nums.push(fun(op.pop(), a, b));
        }

        long res = nums.pop();
        System.out.println(res);
    }

    public static int check(char op){
        if (op == '+' || op == '-'){
            return 1;
        } else if (op == '*'){
            return 2;
        }

        return 0;
    }

    public static long fun(char op, long a, long b){
        if (op == '+'){
            return a + b;
        } else if (op == '-'){
            return a - b;
        } else if (op == '*'){
            return a * b;
        }

        return 0;
    }
}