符号运算 - 华为OD统一考试

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

给定一个表达式，求其分数计算结果

表达式的限制如下：

所有的输入数字皆为正整数(包括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 加个 0for (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 位置开始后面的连续数字整体取出，加入 numswhile (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 mathclass Fraction:def __init__(self, fz, fm):self.fz = fz  # 分子self.fm = fm  # 分母# 加法def add(self, other):nfz = self.fz * other.fm + other.fz * self.fmnfm = self.fm * other.fmreturn Fraction(nfz, nfm).simplify()# 减法def subtract(self, other):nfz = self.fz * other.fm - other.fz * self.fmnfm = self.fm * other.fmreturn Fraction(nfz, nfm).simplify()# 乘法def multiply(self, other):nfz = self.fz * other.fznfm = self.fm * other.fmreturn Fraction(nfz, nfm).simplify()# 触发def divide(self, other):if other.fz == 0:raise RuntimeError("ERROR")nfz = self.fz * other.fmnfm = self.fm * other.fzreturn 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 = "-" + rsreturn rsclass 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 加个 0i = 0while i < n:c = cs[i]if c == '(':ops.append(c)elif c == ')':# 计算到最近一个左括号为止while ops:if ops[-1] != '(':self.calc(nums, ops)else:ops.pop()breakelse:if c.isdigit():u, j = 0, i# 将从 i 位置开始后面的连续数字整体取出，加入 numswhile j < n and cs[j].isdigit():u = u * 10 + int(cs[j])j += 1nums.append(Fraction(u, 1))i = j - 1else: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:breakops.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:returnb = 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 加个 0for (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 位置开始后面的连续数字整体取出，加入 numswhile (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;
}