题目描述
已知火星人使用的运算符为#、$，其与地球人的等价公式如下： x#y = 2x+3y+4 x$y = 3*x+y+2 1、其中x、y是无符号整数 2、地球人公式按C语言规则计算 3、火星人公式中，$的优先级高于#，相同的运算符，按从左到右的顺序计算 现有一段火星人的字符串报文，请你来翻译并计算结果。
题目要求
输入描述: 火星人字符串表达式（结尾不带回车换行） 输入的字符串说明： 字符串为仅由无符号整数和操作符（#、$）组成的计算表达式。例如：123#4$5#67$78。
用例保证字符串中，操作数与操作符之间没有任何分隔符。
用例保证操作数取值范围为32位无符号整数。
保证输入以及计算结果不会出现整型溢出。
保证输入的字符串为合法的求值报文，例如：123#4$5#67$78
保证不会出现非法的求值报文，例如类似这样字符串： *
#4$5 //缺少操作数
4$5# //缺少操作数
4#$5 //缺少操作数
4 $5 //有空格
3+4-5*6/7 //有其它操作符
12345678987654321$54321 //32位整数计算溢出
输出描述: 根据输入的火星人字符串输出计算结果（结尾不带回车换行）
示例1
输入 7#6$5#12 输出 226
示例：
7#6$5#12 =7#(3*6+5+2)#12 =7#25#12 =(2*7+3*25+4)#12 =93#12 =2*93+3*12+4 =226
JAVA解法
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String expr = sc.nextLine().trim();
System.out.print(evaluate(expr));
sc.close();
}
private static long evaluate(String s) {
Deque<Long> nums = new ArrayDeque<>();
Deque<Character> ops = new ArrayDeque<>();
int i = 0;
while (i < s.length()) {
char ch = s.charAt(i);
if (ch == '#' || ch == '$') {
while (!ops.isEmpty() && priority(ops.peek()) >= priority(ch)) {
calc(nums, ops);
}
ops.push(ch);
i++;
} else {
long num = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
i++;
}
nums.push(num);
}
}
while (!ops.isEmpty()) {
calc(nums, ops);
}
return nums.pop();
}
private static int priority(char op) {
return op == '$' ? 2 : 1; // $ 优先级高于 #
}
private static void calc(Deque<Long> nums, Deque<Character> ops) {
long b = nums.pop();
long a = nums.pop();
char op = ops.pop();
long res = (op == '#') ? (2 * a + 3 * b + 4) : (3 * a + b + 2);
nums.push(res);
}
}