(新卷,100分)- 火星文计算2（Java JS Python 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语言的正则表达式操作较为繁琐，且缺乏内置的字符串替换功能，建议采用基于栈的解决方案：

1. 定义一个栈(stack)用于存储操作数和运算符
2. 定义一个操作数容器(operNum)用于收集数字字符
3. 遍历输入字符串中的每个字符c：
   • 若c为数字，则将其存入操作数容器operNum
     （示意图可参考下图）

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

1. 我们完成了某个操作数所有字符的收集，比如
   
   
   
   此时，我们应该检查stack是否为空，如果为空，则操作数直接入栈，然后清空操作数容器，方便接收下一个操作数。
   
   之后将操作符入栈
   
2. 如果stack不为空且stack栈顶是#，比如：
   
   
   
   则此时我们应该进行#运算，即取出栈顶的#后，再取出栈顶元素作为操作数 x，而当前操作数缓存容器operNum中的数值也完成了收集，且可以当作操作数y，然后带入#运算公式。
   
   #运算完成后，我们需要将运算结果重新压入栈中。并且需要清空operNum容器，以及将当前扫描的操作符入栈
   
3. 之后继续走逻辑
   

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

之后继续逻辑：

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

完成#运算后：

1. 检查栈大小：

   • 若 stack.size == 1，栈中仅剩一个操作数，可直接作为结果返回
   • 若 stack.size > 1，栈中至少包含两个操作数和一个$运算符

2. 多元素处理流程：

   • 从栈底取出第一个元素作为初始值x
   • 循环执行以下步骤直至栈为空： a. 取出栈底的$运算符 b. 取出栈底的操作数y c. 执行x$y运算，结果存入x
   • 循环结束后，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] = {'\0'}; int operNum_size = 0; int i = 0; while (s[i] != '\0') { if (s[i] == '#' || s[i] == '$') { // 遇到操作符，则尝试进行#运算 check(stack, operNum); // 如果s[i]是最后一个字符，即我们手动加到尾部的$，则此时直接结束循环，避免之前添加的收尾$进入stack if (s[i + 1] == '\0') break; // 否则，清空操作数缓存容器 memset(operNum, '\0', 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; }