【华为OD机试真题2023 C&D卷 Python&C++】符号运算

川长思鸟来 2024-02-05 16:46 25阅读 0赞

> ## 华为OD2023（C&D卷）机试题库全覆盖，刷题指南点[这里][Link 1] ##

> ## 符号运算 ##
> 
> 时间限制：1s 空间限制：32MB 限定语言：不限
> 
> ### 题目描述： ###
> 
> 给定一个表达式，求其分数计算结果  
> 
> 
> 表达式的限制如下：
> 
> 1. 所有的输入数字皆为正整数(包括0)
> 
> 2. 仅支持四则运算(+-\*/)和括号
> 
> 3. 结果为整数或分数, 分数必须化为最简格式(比如6, 3/4, 7/8, 90/7)
> 
> 4. 除数可能为0，如果遇到这种情况，直接输出"ERROR"
> 
> 5. 输入和最终计算结果中的数字都不会超出整型范围
> 
> 用例的输入一定合法, 不会出现括号不匹配的情况
> 
> #### 输入描述： ####
> 
> 字符串格式的表达式，仅支持+-\*/，数字可能超过两位，可能带有空格，没有负数
> 
> 长度小于200个字符
> 
> #### 输出描述： ####
> 
> 表达式结果，以最简格式表达  
> 如果结果为整数，那么直接输出整数
> 
> 如果结果为分数，那么分子分母不可再约分，可以为假分数，不可表达为带分数
> 
> 结果可能是负数, 负号放在最前面

> ### 示例1 ###
> 
> #### 输入： ####
> 
>     1 + 5 * 7 / 8
> 
> #### 输出： ####
> 
>     43/8
> 
> ### 示例2 ###
> 
> #### 输入： ####
> 
>     1 / (0 - 5)
> 
> #### 输出： ####
> 
>     -1/5
> 
> #### 说明： ####
> 
> 负号需要提到最前面
> 
> ### 示例3 ###
> 
> #### 输入： ####
> 
>     1 * (3*4/(8-(7+0)))
> 
> #### 输出： ####
> 
>     12
> 
> #### 说明： ####
> 
> 注意括号可以多重嵌套

> ### 解题思路： ###
> 
> 这道题主要还是在处理分数逻辑上有点乱。需要求最小公倍数和最大公约数来处理分子分母。我们的算法思路就是将所有的数字全部转化为分数，在分数的基础上进行加减乘除。

> ### 代码（Python）： ###
> 
>     from collections import deque
>     def main():
>         #str = input()
>         str = '1 / 2 / 3 / 4 / (5 / 6) / 7 / 8 / 9 / 10'
>         len_str = len(str)
>         deque_str = deque()
>         num = ''
>         isError = False
>         for i in range(len_str):
>             c = str[i]
>             # 如果是数字
>             if c.isdigit():
>                 num += c
>                 if i == len_str - 1:
>                     # 判断符号
>                     fuhao = deque_str[-1] if deque_str else ''
>                     # 如果符号是乘除，则需要计算
>                     if fuhao == '*' or fuhao == '/':
>                         if fuhao == '/' and num == '0':
>                             isError = True
>                             break
>                         fuhao = deque_str.pop()
>                         deque_str.append(jisuan(deque_str.pop(), fuhao, num))
>                     else:
>                         deque_str.append(num)
>             elif c == '(':
>                 deque_str.append(c)
>             elif c == ')':
>                 if num == '':
>                     sum = deque_str.pop()
>                 else:
>                     sum = num
>                     num = ''
>                 while deque_str[-1] != '(':
>                     fuhao = deque_str.pop()
>                     temp = deque_str.pop()
>                     sum = jisuan(temp, fuhao, sum)
>                 # 左括号删除
>                 deque_str.pop()
>                 # 判读左括号前的符号
>                 fuhao = deque_str[-1] if deque_str else ''
>                 # 如果符号是乘除，则需要计算
>                 if fuhao and (fuhao == '*' or fuhao == '/'):
>                     if fuhao == '/' and sum == '0':
>                         isError = True
>                         break
>                     fuhao = deque_str.pop()
>                     deque_str.append(jisuan(deque_str.pop(), fuhao, sum))
>                 else:
>                     deque_str.append(sum)
>             elif c == ' ':
>                 continue
>             else:
>                 # 判断符号
>                 fuhao = deque_str[-1] if deque_str else ''
>                 # 如果符号是乘除，则需要计算
>                 if fuhao and (fuhao == '*' or fuhao == '/'):
>                     if fuhao == '/' and num == '0':
>                         isError = True
>                         break
>                     fuhao = deque_str.pop()
>                     deque_str.append(jisuan(deque_str.pop(), fuhao, num))
>                 elif num != '':
>                     deque_str.append(num)
>                 # 本次的符号也需要加入
>                 deque_str.append(c)
>                 # num置空
>                 num = ''
>     
>         if isError:
>             print('ERROR')
>         else:
>             res = deque_str.popleft()
>             while deque_str:
>                 res = jisuan(res, deque_str.popleft(), deque_str.popleft())
>     
>             print(res)
>     
>     def jisuan(a, fuhao, b):
>         as_ = zhuanhua(a)
>         aFZ = int(as_[0])
>         aFM = int(as_[1])
>     
>         bs = zhuanhua(b)
>         if fuhao == '/':
>             # 除号需要倒置分子分母
>             bFZ = int(bs[1])
>             bFM = int(bs[0])
>         else:
>             bFZ = int(bs[0])
>             bFM = int(bs[1])
>     
>         # 最小公约数
>         yueshu, fenzi, fenmu = 0, 0, 0
>         if fuhao == '*' or fuhao == '/':
>             fenzi = aFZ * bFZ
>             fenmu = aFM * bFM
>         else:
>             gongbeishu_ = gongbeishu(aFM, bFM)
>             fenmu = gongbeishu_
>             aFZ = gongbeishu_ // aFM * aFZ
>             bFZ = gongbeishu_ // bFM * bFZ
>             if fuhao == '+':
>                 fenzi = aFZ + bFZ
>             else:
>                 fenzi = aFZ - bFZ
>     
>         if fenzi == 0:
>             return '0'
>     
>         max_ = max(abs(fenmu), abs(fenzi))
>         min_ = min(abs(fenmu), abs(fenzi))
>         yueshu = zuixiaogongyueshu(max_, min_)
>     
>         fenzi = fenzi // yueshu
>         fenmu = fenmu // yueshu
>     
>         if fenzi % fenmu == 0:
>             return str(fenzi // fenmu)
>         else:
>             if fenmu < 0:
>                 # 分母是负数，则需要将负号移到分子
>                 fenmu = -fenmu
>                 fenzi = -fenzi
>             return str(fenzi) + '/' + str(fenmu)
>     
>     # 将数字转化为分子分母格式
>     def zhuanhua(shuzi):
>         shuzis = shuzi.split('/')
>         szFenzi = shuzis[0]
>         szFenmu = shuzis[1] if len(shuzis) == 2 else '1'
>         return [szFenzi, szFenmu]
>     
>     def zuixiaogongyueshu(a, b):
>         while a % b != 0:
>             b = a % b
>         return b
>     
>     def gongbeishu(a, b):
>         gongyueshu = zuixiaogongyueshu(a, b)
>         return a // gongyueshu * b // gongyueshu * gongyueshu
>     
>     if __name__ == '__main__':
>         main()

> ### 代码（C++）： ###
> 
>     #include <iostream>
>     #include <deque>
>     #include <sstream>
>     
>     using namespace std;
>     
>     string jisuan(string a, string fuhao, string b);
>     
>     string* zhuanhua(string shuzi);
>     
>     int zuixiaogongyueshu(int a, int b);
>     
>     int gongbeishu(int a, int b);
>     
>     int main() {
>         string str;
>         getline(cin, str);
>         //string str = "1 / 2 / 3 / 4 / (5 / 6) / 7 / 8 / 9 / 10";
>         int len = str.length();
>         deque<string> deque;
>         string num = "";
>         bool isError = false;
>         for (int i = 0; i < len; i++) {
>             char c = str[i];
>             //如果是数字
>             if (isdigit(c)) {
>                 num += c;
>                 if (i == len - 1) {
>                     //判断符号
>                     string fuhao = deque.back();
>                     //如果符号是乘除，则需要计算
>                     if (fuhao == "*" || fuhao == "/") {
>                         if (fuhao == "/" && num == "0") {
>                             isError = true;
>                             break;
>                         }
>                         fuhao = deque.back();
>                         deque.pop_back();
>                         deque.push_back(jisuan(deque.back(), fuhao, num));
>                     } else {
>                         deque.push_back(num);
>                     }
>                 }
>             } else if (c == '(') {
>                 deque.push_back(string(1, c));
>             } else if (c == ')') {
>                 string sum;
>                 if (num == "") {
>                     sum = deque.back();
>                     deque.pop_back();
>                 } else {
>                     sum = num;
>                     num = "";
>                 }
>                 while (deque.back() != "(") {
>                     string fuhao = deque.back();
>                     deque.pop_back();
>                     string temp = deque.back();
>                     deque.pop_back();
>                     sum = jisuan(temp, fuhao, sum);
>                 }
>                 //左括号删除
>                 deque.pop_back();
>                 //判读左括号前的符号
>                 string fuhao = deque.back();
>                 //如果符号是乘除，则需要计算
>                 if (fuhao != "" && (fuhao == "*" || fuhao == "/")) {
>                     if (fuhao == "/" && sum == "0") {
>                         isError = true;
>                         break;
>                     }
>                     fuhao = deque.back();
>                     deque.pop_back();
>                     deque.push_back(jisuan(deque.back(), fuhao, sum));
>                 } else {
>                     deque.push_back(sum);
>                 }
>             } else if (c == ' ') {
>                 continue;
>             } else {
>                 //判断符号
>                 string fuhao = deque.back();
>                 //如果符号是乘除，则需要计算
>                 if (fuhao != "" && (fuhao == "*" || fuhao == "/")) {
>                     if (fuhao == "/" && num == "0") {
>                         isError = true;
>                         break;
>                     }
>                     fuhao = deque.back();
>                     deque.pop_back();
>                     deque.push_back(jisuan(deque.back(), fuhao, num));
>                 } else if (num != "") {
>                     deque.push_back(num);
>                 }
>                 //本次的符号也需要加入
>                 deque.push_back(string(1, c));
>                 //num置空
>                 num = "";
>             }
>         }
>         if (isError) {
>             cout << "ERROR" << endl;
>         } else {
>             string res = deque.front();
>             deque.pop_front();
>             while (!deque.empty()) {
>                 res = jisuan(res, deque.front(), deque[1]);
>                 deque.pop_front();
>                 deque.pop_front();
>             }
>             cout << res << endl;
>         }
>         return 0;
>     }
>     
>     string jisuan(string a, string fuhao, string b) {
>         string* as = zhuanhua(a);
>         int aFZ = stoi(as[0]);
>         int aFM = stoi(as[1]);
>         string* bs = zhuanhua(b);
>         int bFZ, bFM;
>         if (fuhao == "/") {
>             //除号需要倒置分子分母
>             bFZ = stoi(bs[1]);
>             bFM = stoi(bs[0]);
>         } else {
>             bFZ = stoi(bs[0]);
>             bFM = stoi(bs[1]);
>         }
>         //最小公约数
>         int yueshu, fenzi, fenmu;
>         if (fuhao == "*" || fuhao == "/") {
>             fenzi = aFZ * bFZ;
>             fenmu = aFM * bFM;
>         } else {
>             int gongbeishu = gongbeishu(aFM, bFM);
>             fenmu = gongbeishu;
>             aFZ = gongbeishu / aFM * aFZ;
>             bFZ = gongbeishu / bFM * bFZ;
>             if (fuhao == "+") {
>                 fenzi = aFZ + bFZ;
>             } else {
>                 fenzi = aFZ - bFZ;
>             }
>         }
>         if (fenzi == 0) {
>             return "0";
>         }
>         int max = max(abs(fenmu), abs(fenzi));
>         int min = min(abs(fenmu), abs(fenzi));
>         yueshu = zuixiaogongyueshu(max, min);
>         fenzi = fenzi / yueshu;
>         fenmu = fenmu / yueshu;
>         if (fenzi % fenmu == 0) {
>             return to_string(fenzi / fenmu);
>         } else {
>             if (fenmu < 0) {
>                 //分母是负数，则需要将负号移到分子
>                 fenmu = -fenmu;
>                 fenzi = -fenzi;
>             }
>             return to_string(fenzi) + '/' + to_string(fenmu);
>         }
>     }
>     
>     string* zhuanhua(string shuzi) {
>         stringstream ss(shuzi);
>         string* shuzis = new string[2];
>         getline(ss, shuzis[0], '/');
>         if (ss.peek() != EOF) {
>             getline(ss, shuzis[1], '/');
>         } else {
>             shuzis[1] = "1";
>         }
>         return shuzis;
>     }
>     
>     int zuixiaogongyueshu(int a, int b) {
>         while (a % b != 0) {
>             b = a % b;
>         }
>         return b;
>     }
>     
>     int gongbeishu(int a, int b) {
>         int gongyueshu = zuixiaogongyueshu(a, b);
>         return a / gongyueshu * b / gongyueshu * gongyueshu;
>     }

[Link 1]: https://blog.csdn.net/qq_34465338/article/details/135069503