符号运算 - 华为OD统一考试（C卷）
OD统一考试（C卷）
分值： 200分
题解： Java / Python / C++
题目描述
给定一个表达式，求其分数计算结果
表达式的限制如下：
- 所有的输入数字皆为正整数(包括0)
- 仅支持四则运算(+-*/)和括号
- 结果为整数或分数, 分数必须化为最简格式(比如6, 3/4, 7/8, 90/7)
- 除数可能为0，如果遇到这种情况，直接输出"ERROR"
- 输入和最终计算结果中的数字都不会超出整型范围
用例的输入一定合法, 不会出现括号不匹配的情况
输入描述
字符串格式的表达式，仅支持+-*/，数字可能超过两位，可能带有空格，没有负数
长度小于200个字符
输出描述
表达式结果，以最简格式表达 如果结果为整数，那么直接输出整数 如果结果为分数，那么分子分母不可再约分，可以为假分数，不可表达为带分数 结果可能是负数, 负号放在最前面
示例1
输入：
1 + 5 * 7 / 8
输出：
43/8
示例2
输入：
1 / (0-5)
输出：
-1/5
示例3
输入：
1 * (3*4/(8-(7+0)))
输出：
12
题解
这是一个计算表达式的题目，涉及到四则运算和括号的处理。主要思路是通过两个栈，一个存放数字，一个存放运算符，按照运算符的优先级进行计算。以下是对代码的一些解释：
Fraction类用于表示分数，包含了分子fz和分母fm，以及一些基本的运算方法（加、减、乘、除）和简化分数的方法。Solution类实现了计算表达式的方法calculate，以及辅助方法calc用于处理运算。- 在
calculate方法中，通过遍历输入的表达式字符数组，根据字符的类型进行相应的处理。如果是数字，则将连续的数字字符组合成一个整数，并添加到数字栈中。如果是运算符，则根据运算符的优先级进行相应的计算。括号的处理通过检测左括号入栈，右括号时计算直到遇到左括号。Fraction类中的simplify方法用于简化分数，使用最大公约数来除去分子分母的公约数，得到最简形式的分数。- 在
calc方法中，根据当前运算符的优先级，判断是否需要进行运算，如果需要则从数字栈中取出两个数字和运算符进行计算，并将结果放回数字栈。- 最终，得到的结果为数字栈中最后剩下的一个分数，输出其最简形式。
关于时间复杂度和空间复杂度：
- 时间复杂度：遍历输入字符串一次，每个字符进行常数时间的操作，因此时间复杂度为 O(n)。
- 空间复杂度：使用两个栈来存放数字和运算符，最坏情况下可能同时存放整个表达式的内容，因此空间复杂度为 O(n)。
Java
import java.util.*;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Solution solution = new Solution();
try {
String s = scanner.nextLine().replaceAll(" ", "");
System.out.println(solution.calculate(s.toCharArray()));
} catch (Exception e) {
System.out.println("ERROR");
}
}
}
class Solution {
Map<Character, Integer> map;
public Solution() {
// 符号优先级
this.map = new HashMap<>();
this.map.put('-', 1);
this.map.put('+', 1);
this.map.put('*', 2);
this.map.put('/', 2);
}
public Fraction calculate(char[] cs) {
int n = cs.length;
Deque<Fraction> nums = new ArrayDeque<>(); // 存放所有的数字
Deque<Character> ops = new ArrayDeque<>(); // 存放所有「非数字以外」的操作
nums.addLast(new Fraction(0, 1)); // 为了防止第一个数为负数，先往 nums 加个 0
for (int i = 0; i < n; i++) {
char c = cs[i];
if (c == '(') {
ops.addLast(c);
} else if (c == ')') {
// 计算到最近一个左括号为止
while (!ops.isEmpty()) {
if (ops.peekLast() != '(') {
calc(nums, ops);
} else {
ops.pollLast();
break;
}
}
} else {
if (isNumber(c)) {
int u = 0, j = i;
// 将从 i 位置开始后面的连续数字整体取出，加入 nums
while (j < n && isNumber(cs[j])) u = u * 10 + (cs[j++] - '0');
nums.addLast(new Fraction(u, 1));
i = j - 1;
} else {
if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
nums.addLast(new Fraction(0, 1));
}
while (!ops.isEmpty() && ops.peekLast() != '(') {
char prev = ops.peekLast();
if (map.get(prev) >= map.get(c)) {
calc(nums, ops);
} else {
break;
}
}
ops.addLast(c);
}
}
}
// 将剩余的计算完
while (!ops.isEmpty()) calc(nums, ops);
return nums.peekLast();
}
void calc(Deque<Fraction> nums, Deque<Character> ops) {
if (nums.size() < 2 || ops.isEmpty()) return;
Fraction b = nums.pollLast(), a = nums.pollLast();
char op = ops.pollLast();
Fraction ans = null;
if (op == '+') ans = a.add(b);
else if (op == '-') ans = a.subtract(b);
else if (op == '*') ans = a.multiply(b);
else if (op == '/') ans = a.divide(b);
nums.addLast(ans);
}
boolean isNumber(char c) {
return Character.isDigit(c);
}
}
/**
* 分数类
*/
class Fraction {
long fz; // 分子
long fm; // 分母
Fraction(long fz, long fm) {
this.fz = fz;
this.fm = fm;
}
// 加法
Fraction add(Fraction other) {
long nfz = this.fz * other.fm + other.fz * this.fm;
long nfm = this.fm * other.fm;
return new Fraction(nfz, nfm).simplify();
}
// 减法
Fraction subtract(Fraction other) {
long nfz = this.fz * other.fm - other.fz * this.fm;
long nfm = this.fm * other.fm;
return new Fraction(nfz, nfm).simplify();
}
// 乘法
Fraction multiply(Fraction other) {
long nfz = this.fz * other.fz;
long nfm = this.fm * other.fm;
return new Fraction(nfz, nfm).simplify();
}
// 除法
Fraction divide(Fraction other) {
if (other.fz == 0) throw new ArithmeticException("ERROR");
long nfz = this.fz * other.fm;
long nfm = this.fm * other.fz;
return new Fraction(nfz, nfm).simplify();
}
// 简化分母
Fraction simplify() {
long gcd = gcd(this.fz, this.fm);
return new Fraction(this.fz / gcd, this.fm / gcd);
}
// 求两个数的最小公倍数
public long gcd(long a, long b) {
return a % b == 0 ? b : gcd(b, a % b);
}
public String toString() {
if (fm == 1) {
return Long.toString(fz);
} else {
String rs = Math.abs(fz) + "/" + Math.abs(fm);
if (fz * fm < 0) rs = "-" + rs;
return rs;
}
}
}
Python
import math
class Fraction:
def __init__(self, fz, fm):
self.fz = fz # 分子
self.fm = fm # 分母
# 加法
def add(self, other):
nfz = self.fz * other.fm + other.fz * self.fm
nfm = self.fm * other.fm
return Fraction(nfz, nfm).simplify()
# 减法
def subtract(self, other):
nfz = self.fz * other.fm - other.fz * self.fm
nfm = self.fm * other.fm
return Fraction(nfz, nfm).simplify()
# 乘法
def multiply(self, other):
nfz = self.fz * other.fz
nfm = self.fm * other.fm
return Fraction(nfz, nfm).simplify()
# 除法
def divide(self, other):
if other.fz == 0:
raise RuntimeError("ERROR")
nfz = self.fz * other.fm
nfm = self.fm * other.fz
return Fraction(nfz, nfm).simplify()
# 简化分母
def simplify(self):
gcd_val = self.gcd(abs(self.fz), abs(self.fm))
return Fraction(self.fz // gcd_val, self.fm // gcd_val)
# 求两个数的最大公约数
def gcd(self, a, b):
return a if b == 0 else self.gcd(b, a % b)
def to_string(self):
if self.fm == 1:
return str(self.fz)
else:
rs = str(abs(self.fz)) + "/" + str(abs(self.fm))
if self.fz * self.fm < 0:
rs = "-" + rs
return rs
class Solution:
def __init__(self):
# 符号优先级
self.map = {'-': 1, '+': 1, '*': 2, '/': 2}
def calculate(self, cs):
n = len(cs)
nums = [] # 存放所有的数字
ops = [] # 存放所有「非数字以外」的操作
nums.append(Fraction(0, 1)) # 为了防止第一个数为负数，先往 nums 加个 0
i = 0
while i < n:
c = cs[i]
if c == '(':
ops.append(c)
elif c == ')':
# 计算到最近一个左括号为止
while ops:
if ops[-1] != '(':
self.calc(nums, ops)
else:
ops.pop()
break
else:
if c.isdigit():
u, j = 0, i
# 将从 i 位置开始后面的连续数字整体取出，加入 nums
while j < n and cs[j].isdigit():
u = u * 10 + int(cs[j])
j += 1
nums.append(Fraction(u, 1))
i = j - 1
else:
if i > 0 and (cs[i - 1] == '(' or cs[i - 1] == '+' or cs[i - 1] == '-'):
nums.append(Fraction(0, 1))
while ops and ops[-1] != '(':
prev = ops[-1]
if self.map[prev] >= self.map[c]:
self.calc(nums, ops)
else:
break
ops.append(c)
i += 1
# 将剩余的计算完
while ops:
self.calc(nums, ops)
return nums[-1]
def calc(self, nums, ops):
if len(nums) < 2 or not ops:
return
b = nums.pop() # 弹出数字
a = nums.pop() # 弹出数字
op = ops.pop() # 弹出操作符
if op == '+':
nums.append(a.add(b))
elif op == '-':
nums.append(a.subtract(b))
elif op == '*':
nums.append(a.multiply(b))
elif op == '/':
nums.append(a.divide(b))
if __name__ == "__main__":
solution = Solution()
expression = input().replace(" ", "") # 移除空格
try:
result = solution.calculate(expression)
print(result.to_string())
except Exception as e:
print("ERROR")
C++
#include <bits/stdc++.h>
using namespace std;
class Fraction {
public:
long fz; // 分子
long fm; // 分母
Fraction(long fz, long fm) : fz(fz), fm(fm) {}
// 加法
Fraction add(const Fraction& other) const {
long nfz = this->fz * other.fm + other.fz * this->fm;
long nfm = this->fm * other.fm;
return Fraction(nfz, nfm).simplify();
}
// 减法
Fraction subtract(const Fraction& other) const {
long nfz = this->fz * other.fm - other.fz * this->fm;
long nfm = this->fm * other.fm;
return Fraction(nfz, nfm).simplify();
}
// 乘法
Fraction multiply(const Fraction& other) const {
long nfz = this->fz * other.fz;
long nfm = this->fm * other.fm;
return Fraction(nfz, nfm).simplify();
}
// 除法
Fraction divide(const Fraction& other) const {
if (other.fz == 0) throw runtime_error("ERROR");
long nfz = this->fz * other.fm;
long nfm = this->fm * other.fz;
return Fraction(nfz, nfm).simplify();
}
// 简化分母
Fraction simplify() const {
long gcd_val = gcd(abs(fz), abs(fm));
return Fraction(fz / gcd_val, fm / gcd_val);
}
// 求两个数的最大公约数
long gcd(long a, long b) const {
return (b == 0) ? a : gcd(b, a % b);
}
string toString() const {
if (fm == 1) {
return to_string(fz);
} else {
string rs = to_string(abs(fz)) + "/" + to_string(abs(fm));
if (fz * fm < 0) rs = "-" + rs;
return rs;
}
}
};
class Solution {
public:
unordered_map<char, int> map;
Solution() {
// 符号优先级
map['-'] = 1;
map['+'] = 1;
map['*'] = 2;
map['/'] = 2;
}
Fraction calculate(const char* cs) {
int n = strlen(cs);
deque<Fraction> nums; // 存放所有的数字
deque<char> ops; // 存放所有「非数字以外」的操作
nums.push_back(Fraction(0, 1)); // 为了防止第一个数为负数，先往 nums 加个 0
for (int i = 0; i < n; i++) {
char c = cs[i];
if (c == '(') {
ops.push_back(c);
} else if (c == ')') {
// 计算到最近一个左括号为止
while (!ops.empty()) {
if (ops.back() != '(') {
calc(nums, ops);
} else {
ops.pop_back();
break;
}
}
} else {
if (isdigit(c)) {
int u = 0, j = i;
// 将从 i 位置开始后面的连续数字整体取出，加入 nums
while (j < n && isdigit(cs[j])) u = u * 10 + (cs[j++] - '0');
nums.push_back(Fraction(u, 1));
i = j - 1;
} else {
if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
nums.push_back(Fraction(0, 1));
}
while (!ops.empty() && ops.back() != '(') {
char prev = ops.back();
if (map[prev] >= map[c]) {
calc(nums, ops);
} else {
break;
}
}
ops.push_back(c);
}
}
}
// 将剩余的计算完
while (!ops.empty()) calc(nums, ops);
return nums.back();
}
void calc(deque<Fraction>& nums, deque<char>& ops) {
if (nums.size() < 2 || ops.empty()) return;
Fraction b = nums.back(); nums.pop_back();
Fraction a = nums.back(); nums.pop_back();
char op = ops.back(); ops.pop_back();
if (op == '+') nums.push_back(a.add(b));
else if (op == '-') nums.push_back(a.subtract(b));
else if (op == '*') nums.push_back(a.multiply(b));
else if (op == '/') nums.push_back(a.divide(b));
}
};
int main() {
Solution solution;
char buffer[210];
cin.getline(buffer, sizeof(buffer));
string s(buffer);
s.erase(remove_if(s.begin(), s.end(), ::isspace), s.end()); // 移除空格
try {
Fraction result = solution.calculate(s.c_str());
cout << result.toString() << endl;
} catch (const exception& e) {
cout << "ERROR" << endl;
}
return 0;
}
相关练习题
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
#面经##华为##春招##秋招##社招#