(C卷,100分)- 火星文计算2（Java & JS & Python & C）

题目描述

已知火星人使用的运算符为#、$，其与地球人的等价公式如下：

• x#y = 4*x+3*y+2
• x$y = 2*x+y+3

1. 其中 x、y 是无符号整数
2. 地球人公式按C语言规则计算
3. 火星人公式中，#的优先级高于$，相同的运算符，按从左到右的顺序计算

现有一段火星人的字符串报文，请你来翻译并计算结果。

输入描述

火星人字符串表达式（结尾不带回车换行）

输入的字符串说明：  字符串为仅由无符号整数和操作符（#、$）组成的计算表达式。例如：

123#4$5#67$78

1. 用例保证字符串中，操作数与操作符之间没有任何分隔符。  
2. 用例保证操作数取值范围为32位无符号整数。  
3. 保证输入以及计算结果不会出现整型溢出。  
4. 保证输入的字符串为合法的求值报文，例如：123#4$5#67$78  
5. 保证不会出现非法的求值报文，例如类似这样字符串：  

   #4$5                                             //缺少操作数  

   4$5#                                             //缺少操作数  

   4#$5                                             //缺少操作数  

   4 $5                                              //有空格  

   3+4-5*6/7                                     //有其它操作符  

   12345678987654321$54321       //32位整数计算溢出

输出描述

根据输入的火星人字符串输出计算结果（结尾不带回车换行）

用例

题目解析

本题和下面题目基本一致

只是#和$的替换公式，以及优先级改变了。

Java、JS、Python语言的题解可以参考上面博客。

由于C语言的正则操作十分繁琐，以及没有内置的字符串替换操作，因此C语言建议使用栈解法：

• 首先我们需要定义一个栈stack，用于记录操作数和操作符，
• 然后定义一个操作数容器operNum，由于收集操作数的数字字符，

接下来开始遍历输入字符串的每一个字符c：

• 如果 c 是数字，则收集进操作数容器operNum，如下图所示

  

• 如果 c 不是数字，即#或$，那么此时有两个信息：

1. 我们完成了某个操作数所有字符的收集，比如

   

   此时，我们应该检查stack是否为空，如果为空，则操作数直接入栈，然后清空操作数容器，方便接收下一个操作数。

   之后将操作符入栈

   

2. 如果stack不为空且stack栈顶是#，比如：

   

   则此时我们应该进行#运算，即取出栈顶的#后，再取出栈顶元素作为操作数 x，而当前操作数缓存容器operNum中的数值也完成了收集，且可以当作操作数y，然后带入#运算公式。

   #运算完成后，我们需要将运算结果重新压入栈中。并且需要清空operNum容器，以及将当前扫描的操作符入栈

   

3. 之后继续走逻辑

   

如果扫描到运算符，则需要检查stack栈顶是否为#运算，若不是，则直接将operNum和当前扫描的操作符入栈

之后继续逻辑：

此时扫描到了输入字符串的尾部，并且operNum完成了最后一个操作数的收集。此时我们需要将最后一个操作数入栈，入栈前还需要检查栈顶是否为#，若是，则取出栈顶两个元素，按照前面逻辑进行#运算，

完成#运算后：

• 如果stack.size == 1，则栈中只剩下一个操作，此时可以直接当成结果返回。
• 如果stack.size > 1，则栈中至少有两个操作数以及一个$，接下里应该进行$运算逻辑：

1. 首先我们应该从栈底取出一个元素作为x
2. 之后循环逻辑：先取出栈底的操作符$，再取出栈底的操作数y，然后进行$运算，并将运算结果赋值给x，即运算结果作为新的操作数x，然后继续循环逻辑，直到stack为空时结束。

最后x中记录的值即为结果。

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const path = require("path");
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  console.log(getResult(line));
});

function getResult(str) {
  const regExp = /(d+)#(d+)/;

  while (str.indexOf("#") !== -1) {
    str = str.replace(
      regExp,
      (_, x, y) => 4 * parseInt(x) + 3 * parseInt(y) + 2
    );
  }

  return str.split("$").reduce((x, y) => 2 * parseInt(x) + parseInt(y) + 3);
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String str = sc.next();
    System.out.print(getResult(str));
  }

  public static long getResult(String str) {
    Pattern p = Pattern.compile("(\d+)#(\d+)");

    while (true) {
      Matcher m = p.matcher(str);
      if (!m.find()) break;

      String subStr = m.group(0);
      long x = Long.parseLong(m.group(1));
      long y = Long.parseLong(m.group(2));
      str = str.replaceFirst(subStr, 4 * x + 3 * y + 2 + "");
    }

    return Arrays.stream(str.split("\$"))
        .map(Long::parseLong)
        .reduce((x, y) -> 2 * x + y + 3)
        .orElse(0L);
  }
}

Python算法源码

import re

# 输入获取
s = input()


# 算法入口
def getResult(s):
    p = re.compile("(\d+)#(\d+)")

    while True:
        m = p.search(s)
        if m:
            subS = m.group()
            x = int(m.group(1))
            y = int(m.group(2))
            # 注意这里replace只能进行替换第一次出现的，不能替换多次，因此replace方法第三个参数为1，表示只替换首次匹配
            s = s.replace(subS, str(4 * x + 3 * y + 2), 1)
        else:
            break

    arr = list(map(int, s.split("$")))

    x = arr[0]
    for y in arr[1:]:
        x = 2 * x + y + 3

    return x


# 算法调用
print(getResult(s))

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_INPUT_LEN 10000
#define MAX_NUM_LEN 100

typedef struct ListNode {
    char ele[MAX_NUM_LEN];
    struct ListNode *prev;
    struct ListNode *next;
} ListNode;

typedef struct LinkedList {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));
    link->size = 0;
    link->head = NULL;
    link->tail = NULL;
    return link;
}

void addLast_LinkedList(LinkedList *link, char *ele) {
    ListNode *node = (ListNode *) malloc(sizeof(ListNode));
    strcpy(node->ele, ele);
    node->prev = NULL;
    node->next = NULL;

    if (link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        link->tail->next = node;
        node->prev = link->tail;
        link->tail = node;
    }

    link->size++;
}

char *removeFirst_LinkedList(LinkedList *link) {
    if (link->size == 0) exit(-1);

    ListNode *removed = link->head;

    if (link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->head = link->head->next;
        link->head->prev = NULL;
    }

    link->size--;

    char *res = (char *) calloc(MAX_NUM_LEN, sizeof(char));
    strcpy(res, removed->ele);

    free(removed);

    return res;
}

char *removeLast_LinkedList(LinkedList *link) {
    if (link->size == 0) exit(-1);

    ListNode *removed = link->tail;

    if (link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->tail = link->tail->prev;
        link->tail->next = NULL;
    }

    link->size--;

    char *res = (char *) calloc(MAX_NUM_LEN, sizeof(char));
    strcpy(res, removed->ele);

    free(removed);

    return res;
}

// 尝试进行#运算
void check(LinkedList *stack, char *operNum2) {
    // 如果栈顶元素是"#"号, 则可以进行#运算
    if (stack->size > 0 && strcmp(stack->tail->ele, "#") == 0) {
        // 取出栈顶的"#"
        removeLast_LinkedList(stack);
        // 取出操作数x
        char *operNum1 = removeLast_LinkedList(stack);

        long long x = atoll(operNum1);
        long long y = atoll(operNum2);

        // 将4 * x + 3 * y + 2包装为字符串
        char res[MAX_NUM_LEN];
        sprintf(res, "%lld", 4 * x + 3 * y + 2);

        // 将计算结果加入栈
        addLast_LinkedList(stack, res);
    } else {
        // 如果栈顶元素不是#，那么操作数2直接入栈
        addLast_LinkedList(stack, operNum2);
    }
}

int main() {
    char s[MAX_INPUT_LEN];
    gets(s);

    strcat(s, "$"); // 末尾加一个$方便后续收尾处理

    LinkedList *stack = new_LinkedList();

    // 操作数缓存容器
    char operNum[MAX_NUM_LEN] = {''};
    int operNum_size = 0;

    int i = 0;
    while (s[i] != '') {

        if (s[i] == '#' || s[i] == '$') {
            // 遇到操作符，则尝试进行#运算
            check(stack, operNum);

            // 如果s[i]是最后一个字符，即我们手动加到尾部的$，则此时直接结束循环，避免之前添加的收尾$进入stack
            if (s[i + 1] == '') break;

            // 否则，清空操作数缓存容器
            memset(operNum, '', MAX_NUM_LEN);
            operNum_size = 0;

            // 将操作符加入栈
            char operator[2];
            sprintf(operator, "%c", s[i]);
            addLast_LinkedList(stack, operator);
        } else {
            // 收集操作数
            operNum[operNum_size++] = s[i];
        }

        i++;
    }

    // 此时，栈中只会剩下 操作数和$
    // 取出栈底元素作为操作数x
    long long x = atoll(removeFirst_LinkedList(stack));

    while (stack->size > 1) {
        // 取出操作符$
        removeFirst_LinkedList(stack);
        // 取出操作数y
        long long y = atoll(removeFirst_LinkedList(stack));
        // 进行$运算，并将运算结果作为新的操作数x
        x = 2 * x + y + 3;
    }

    printf("%lld", x);

    return 0;
}