【栈】2024E-火星文计算2
【栈】2024E-火星文计算2
[P2607] 【栈】2024E-火星文计算2
本题练习地址：https://www.algomooc.com/problem/P2607
题目描述
已知火星人使用的运算符号为 # 、$
他们与地球人的等价公式如下：
x#y = 4*x+3*y+2x$y = 2*x+y+3
其中 x y 是无符号整数
地球人公式按照 C 语言规则进行计算
火星人公式中 # 符优先级高于 $
相同的运算符按从左到右的顺序运算
输入描述
火星人字符串表达式结尾不带回车换行
输入的字符串说明：
字符串为仅有无符号整数和操作符组成的计算表达式
- 用例保证字符串中操作数与操作符之间没有任何分隔符
- 用例保证操作数取值范围为
32位无符号整数 - 保证输入以及计算结果不会出现整型溢出
- 保证输入的字符串为合法的求值报文 例如:
123#4$5#76$78 - 保证不会出现非法的求值报文
例如：
#4$5这种缺少操作数；4$5#这种缺少操作数；4#$5这种缺少操作数；4 $5有空格；3+4-5*6/7有其他操作符；12345678987654321$5432132 位整数溢出
输出描述
根据火星人字符串输出计算结果，结尾不带回车换行
示例
输入
7#6$5#12输出
157说明
7#6$5#12=(4*7+3*6+2)$5#12
=48$5#12
=48$(4*5+3*12+2)
=48$58
=2*48+58+3
=157解题思路
这是一个非常典型的中缀表达式求值类的问题，类似于LC224. 基本计算器，LeetCode227. 基本计算器II。
对于这类表达式求值相关的栈题，我们通常需要考虑以下问题：
- 遇到数字应该如何处理？
- 遇到运算符应该如何处理？
- 何时进行入栈？
- 何时进行出栈以及运算操作？
- 退出循环后如何处理栈中内容？
问题1：遇到数字应该如何处理？
数字显然应该暂存在栈中，等待后续出栈进行运算。
由于需要处理数字不止一位数的情况，我们可以通过构建一个初始值为0的变量num，通过num = num * 10 + int(ch)的方式来更新数字。
这个技巧在很多类似题目都多次出现。
问题2：遇到运算符应该如何处理？
题目告知，两种运算符中，# 的优先级高于 $。
思考小学数学的四则运算，* 的优先级高于 +。
我们在做数学四则运算的时候，总是会先处理乘除，再处理加减。
如果这道题的#是*，$是+，那么我们可以这样处理：
遇到+直接跳过（符号不入栈），把所有*运算处理完毕后，将栈中的所有元素进行求和即可。
（因为除了*，剩下的+，可以直接求和）
因此这道题也是类似，我们必须把#都处理了，再处理$。
遇到$直接跳过（符号不入栈），把所有#运算处理完毕后，在考虑最终的栈中情况（问题5）
问题3：何时进行入栈操作？
在前一点中其实已经提到，遇到符号的时候是不进行入栈的。
但是，遇到符号的时候意味着一个数字已经完全取得了。
因此，数字的入栈时机是在遇到一个符号的时候，我们必须把之前得到的num入栈，同时重置数字num = 0
问题4：何时进行出栈以及运算操作？
出栈意味着运算。
考虑中缀表达式
12#34$56#78如果我们想要计算12#34的结果，其实是不能在遍历到 # 的时候来计算的，因为这个时候我们并不知道 # 后面紧跟着的数字是什么。
也不能在遍历到数字3或4的时候来做计算，因为此时我们并不知道这个数字的位数是多少，无法确定当前得到的数字num就是我们想要的数字。
因此，进行出栈和计算的时机，一定是当遍历到一个新的符号的时候，也就是遍历到$的时候，才需要进行计算。
又结合上述的问题2，我们在第一次遍历的过程中，只需要计算#，所以我们可以使用一个布尔型变量pre_sign_well来标记上一个运算符是否为#。
该变量初始化为False，表示在遇到第一个数字的时候，肯定是不用进行出栈操作和运算的。
只有在遇到一个运算符，且发现上一个运算符是#的时候，也就是pre_sign_well = True的时候，才需要进行出栈和运算，且需要把运算结果重新压回栈中。
然后我们还需要根据新遇到的运算符，修改pre_sign_well的值。
另外根据问题3和4，原式子中的最后一个字符是数字，如果想要正确地取出最后一个数字并进行运算，我们可以在原式子末尾增加一个非数字字符，或者在循环过程中判断是否已经遍历到最后一个字符。
问题5：退出循环后如何处理栈中内容？
退出循环后，原式子中的所有#运算符都已经处理完毕，栈中剩余元素都需要进行$运算。
和简单的+不同，我们不能够直接求和，我们再次对栈中所有元素进行循环，依次进行$运算即可。
代码
Python
# 题目：【栈】2024E-火星文计算2
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：栈
# 代码看不懂的地方，请直接在群上提问
# 根据"#"进行计算
def cal_well(x, y):
return 4 * x + 3 * y + 2
# 根据"$"进行计算
def cal_dollar(x, y):
return 2 * x + y + 3
s = input()
stack = list()
# 一个标记，用于表示上一个计算符号是否是"#"
# 初始化为False
pre_sign_well = False
# 初始化遍历过程中储存的数字
num = 0
# 由于s的最后一个元素必定是数字
# 而运算是在遍历到非数字字符的时候才进行的
# 因此在遍历到最后的数字的时候
# 无法正确地对这个数字进行运算
# 因此在s的末尾加上一个空格
# 用于处理最后一个数字的情况
s += " "
# 遍历ch中的所有字符s
for ch in s:
# 如果ch是数字，则更新num
if ch.isdigit():
num = num * 10 + int(ch)
# 如果ch是字符，即"#"或"$"或空格" "
else:
# 则将num加入栈中，且重置num的值为0
stack.append(num)
num = 0
# 如果在这个符号之前的上一个符号是"#"
# 根据计算的优先级，需要对栈顶的两个元素进行计算
if pre_sign_well:
y = stack.pop()
x = stack.pop()
res = cal_well(x, y)
stack.append(res)
# 如果当前符号ch是"#"，则设置pre_sign_well为True
# 下次遇到非数字字符时，进行计算
pre_sign_well = (ch == "#")
# 退出循环后，栈中剩余若干元素，这些元素得进行"$"号的计算
# 对栈中所有的元素进行cal_dollar()函数的计算
ans = stack[0]
for y in stack[1:]:
ans = cal_dollar(ans, y)
print(ans)Java
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
Stack<Integer> stack = new Stack<>();
boolean preSignWell = false;
int num = 0;
// 在字符串末尾加一个空格，用于处理最后一个数字的情况
s += " ";
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
num = num * 10 + Character.getNumericValue(ch);
} else {
stack.push(num);
num = 0;
if (preSignWell) {
int y = stack.pop();
int x = stack.pop();
int res = calWell(x, y);
stack.push(res);
}
preSignWell = (ch == '#');
}
}
int ans = stack.get(0);
for (int i = 1; i < stack.size(); i++) {
int y = stack.get(i);
ans = calDollar(ans, y);
}
System.out.println(ans);
}
private static int calWell(int x, int y) {
return 4 * x + 3 * y + 2;
}
private static int calDollar(int x, int y) {
return 2 * x + y + 3;
}
}C++
#include <iostream>
#include <vector>
using namespace std;
int calWell(int x, int y) {
return 4 * x + 3 * y + 2;
}
int calDollar(int x, int y) {
return 2 * x + y + 3;
}
int main() {
string s;
getline(cin, s);
vector<int> vec;
bool preSignWell = false;
int num = 0;
// 在字符串末尾加一个空格，用于处理最后一个数字的情况
s += " ";
for (char ch : s) {
if (isdigit(ch)) {
num = num * 10 + (ch - '0');
} else {
vec.push_back(num);
num = 0;
if (preSignWell) {
int y = vec[vec.size() - 1];
vec.pop_back();
int x = vec[vec.size() - 1];
vec.pop_back();
int res = calWell(x, y);
vec.push_back(res);
}
preSignWell = (ch == '#');
}
}
int ans = vec[0];
for (int i = 1; i < vec.size(); i++) {
int y = vec[i];
ans = calDollar(ans, y);
}
cout << ans << endl;
return 0;
}时空复杂度
时间复杂度：O(N)。需要一次遍历每一个字符
空间复杂度：O(N)。栈所需空间。