devbox
爱喝兽奶帝天荒
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【华为OD机试真题2023 C&D卷 Python&C++】符号运算_od考c++可以使用python答题吗

作者：爱喝兽奶帝天荒 | 2024-07-19 23:04:06

赞

踩

od考c++可以使用python答题吗

华为OD2023（C&D卷）机试题库全覆盖，刷题指南点这里

符号运算

时间限制：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）：

  1.  
  2. from collections import deque
  3. def main():
  4.     #str = input()
  5.     str = '1 / 2 / 3 / 4 / (5 / 6) / 7 / 8 / 9 / 10'
  6.     len_str = len(str)
  7.     deque_str = deque()
  8.     num = ''
  9.     isError = False
  10.     for i in range(len_str):
  11.         c = str[i]
  12.         # 如果是数字
  13.         if c.isdigit():
  14.             num += c
  15.             if i == len_str - 1:
  16.                 # 判断符号
  17.                 fuhao = deque_str[-1] if deque_str else ''
  18.                 # 如果符号是乘除，则需要计算
  19.                 if fuhao == '*' or fuhao == '/':
  20.                     if fuhao == '/' and num == '0':
  21.                         isError = True
  22.                         break
  23.                     fuhao = deque_str.pop()
  24.                     deque_str.append(jisuan(deque_str.pop(), fuhao, num))
  25.                 else:
  26.                     deque_str.append(num)
  27.         elif c == '(':
  28.             deque_str.append(c)
  29.         elif c == ')':
  30.             if num == '':
  31.                 sum = deque_str.pop()
  32.             else:
  33.                 sum = num
  34.                 num = ''
  35.             while deque_str[-1] != '(':
  36.                 fuhao = deque_str.pop()
  37.                 temp = deque_str.pop()
  38.                 sum = jisuan(temp, fuhao, sum)
  39.             # 左括号删除
  40.             deque_str.pop()
  41.             # 判读左括号前的符号
  42.             fuhao = deque_str[-1] if deque_str else ''
  43.             # 如果符号是乘除，则需要计算
  44.             if fuhao and (fuhao == '*' or fuhao == '/'):
  45.                 if fuhao == '/' and sum == '0':
  46.                     isError = True
  47.                     break
  48.                 fuhao = deque_str.pop()
  49.                 deque_str.append(jisuan(deque_str.pop(), fuhao, sum))
  50.             else:
  51.                 deque_str.append(sum)
  52.         elif c == ' ':
  53.             continue
  54.         else:
  55.             # 判断符号
  56.             fuhao = deque_str[-1] if deque_str else ''
  57.             # 如果符号是乘除，则需要计算
  58.             if fuhao and (fuhao == '*' or fuhao == '/'):
  59.                 if fuhao == '/' and num == '0':
  60.                     isError = True
  61.                     break
  62.                 fuhao = deque_str.pop()
  63.                 deque_str.append(jisuan(deque_str.pop(), fuhao, num))
  64.             elif num != '':
  65.                 deque_str.append(num)
  66.             # 本次的符号也需要加入
  67.             deque_str.append(c)
  68.             # num置空
  69.             num = ''
  70.  
  71.     if isError:
  72.         print('ERROR')
  73.     else:
  74.         res = deque_str.popleft()
  75.         while deque_str:
  76.             res = jisuan(res, deque_str.popleft(), deque_str.popleft())
  77.  
  78.         print(res)
  79.  
  80. def jisuan(a, fuhao, b):
  81.     as_ = zhuanhua(a)
  82.     aFZ = int(as_[0])
  83.     aFM = int(as_[1])
  84.  
  85.     bs = zhuanhua(b)
  86.     if fuhao == '/':
  87.         # 除号需要倒置分子分母
  88.         bFZ = int(bs[1])
  89.         bFM = int(bs[0])
  90.     else:
  91.         bFZ = int(bs[0])
  92.         bFM = int(bs[1])
  93.  
  94.     # 最小公约数
  95.     yueshu, fenzi, fenmu = 0, 0, 0
  96.     if fuhao == '*' or fuhao == '/':
  97.         fenzi = aFZ * bFZ
  98.         fenmu = aFM * bFM
  99.     else:
  100.         gongbeishu_ = gongbeishu(aFM, bFM)
  101.         fenmu = gongbeishu_
  102.         aFZ = gongbeishu_ // aFM * aFZ
  103.         bFZ = gongbeishu_ // bFM * bFZ
  104.         if fuhao == '+':
  105.             fenzi = aFZ + bFZ
  106.         else:
  107.             fenzi = aFZ - bFZ
  108.  
  109.     if fenzi == 0:
  110.         return '0'
  111.  
  112.     max_ = max(abs(fenmu), abs(fenzi))
  113.     min_ = min(abs(fenmu), abs(fenzi))
  114.     yueshu = zuixiaogongyueshu(max_, min_)
  115.  
  116.     fenzi = fenzi // yueshu
  117.     fenmu = fenmu // yueshu
  118.  
  119.     if fenzi % fenmu == 0:
  120.         return str(fenzi // fenmu)
  121.     else:
  122.         if fenmu < 0:
  123.             # 分母是负数，则需要将负号移到分子
  124.             fenmu = -fenmu
  125.             fenzi = -fenzi
  126.         return str(fenzi) + '/' + str(fenmu)
  127.  
  128. # 将数字转化为分子分母格式
  129. def zhuanhua(shuzi):
  130.     shuzis = shuzi.split('/')
  131.     szFenzi = shuzis[0]
  132.     szFenmu = shuzis[1] if len(shuzis) == 2 else '1'
  133.     return [szFenzi, szFenmu]
  134.  
  135. def zuixiaogongyueshu(a, b):
  136.     while a % b != 0:
  137.         b = a % b
  138.     return b
  139.  
  140. def gongbeishu(a, b):
  141.     gongyueshu = zuixiaogongyueshu(a, b)
  142.     return a // gongyueshu * b // gongyueshu * gongyueshu
  143.  
  144. if __name__ == '__main__':
  145.     main()

代码（C++）：

  1. #include <iostream>
  2. #include <deque>
  3. #include <sstream>
  4.  
  5. using namespace std;
  6.  
  7. string jisuan(string a, string fuhao, string b);
  8.  
  9. string* zhuanhua(string shuzi);
  10.  
  11. int zuixiaogongyueshu(int a, int b);
  12.  
  13. int gongbeishu(int a, int b);
  14.  
  15. int main() {
  16.     string str;
  17.     getline(cin, str);
  18.     //string str = "1 / 2 / 3 / 4 / (5 / 6) / 7 / 8 / 9 / 10";
  19.     int len = str.length();
  20.     deque<string> deque;
  21.     string num = "";
  22.     bool isError = false;
  23.     for (int i = 0; i < len; i++) {
  24.         char c = str[i];
  25.         //如果是数字
  26.         if (isdigit(c)) {
  27.             num += c;
  28.             if (i == len - 1) {
  29.                 //判断符号
  30.                 string fuhao = deque.back();
  31.                 //如果符号是乘除，则需要计算
  32.                 if (fuhao == "*" || fuhao == "/") {
  33.                     if (fuhao == "/" && num == "0") {
  34.                         isError = true;
  35.                         break;
  36.                     }
  37.                     fuhao = deque.back();
  38.                     deque.pop_back();
  39.                     deque.push_back(jisuan(deque.back(), fuhao, num));
  40.                 } else {
  41.                     deque.push_back(num);
  42.                 }
  43.             }
  44.         } else if (c == '(') {
  45.             deque.push_back(string(1, c));
  46.         } else if (c == ')') {
  47.             string sum;
  48.             if (num == "") {
  49.                 sum = deque.back();
  50.                 deque.pop_back();
  51.             } else {
  52.                 sum = num;
  53.                 num = "";
  54.             }
  55.             while (deque.back() != "(") {
  56.                 string fuhao = deque.back();
  57.                 deque.pop_back();
  58.                 string temp = deque.back();
  59.                 deque.pop_back();
  60.                 sum = jisuan(temp, fuhao, sum);
  61.             }
  62.             //左括号删除
  63.             deque.pop_back();
  64.             //判读左括号前的符号
  65.             string fuhao = deque.back();
  66.             //如果符号是乘除，则需要计算
  67.             if (fuhao != "" && (fuhao == "*" || fuhao == "/")) {
  68.                 if (fuhao == "/" && sum == "0") {
  69.                     isError = true;
  70.                     break;
  71.                 }
  72.                 fuhao = deque.back();
  73.                 deque.pop_back();
  74.                 deque.push_back(jisuan(deque.back(), fuhao, sum));
  75.             } else {
  76.                 deque.push_back(sum);
  77.             }
  78.         } else if (c == ' ') {
  79.             continue;
  80.         } else {
  81.             //判断符号
  82.             string fuhao = deque.back();
  83.             //如果符号是乘除，则需要计算
  84.             if (fuhao != "" && (fuhao == "*" || fuhao == "/")) {
  85.                 if (fuhao == "/" && num == "0") {
  86.                     isError = true;
  87.                     break;
  88.                 }
  89.                 fuhao = deque.back();
  90.                 deque.pop_back();
  91.                 deque.push_back(jisuan(deque.back(), fuhao, num));
  92.             } else if (num != "") {
  93.                 deque.push_back(num);
  94.             }
  95.             //本次的符号也需要加入
  96.             deque.push_back(string(1, c));
  97.             //num置空
  98.             num = "";
  99.         }
  100.     }
  101.     if (isError) {
  102.         cout << "ERROR" << endl;
  103.     } else {
  104.         string res = deque.front();
  105.         deque.pop_front();
  106.         while (!deque.empty()) {
  107.             res = jisuan(res, deque.front(), deque[1]);
  108.             deque.pop_front();
  109.             deque.pop_front();
  110.         }
  111.         cout << res << endl;
  112.     }
  113.     return 0;
  114. }
  115.  
  116. string jisuan(string a, string fuhao, string b) {
  117.     string* as = zhuanhua(a);
  118.     int aFZ = stoi(as[0]);
  119.     int aFM = stoi(as[1]);
  120.     string* bs = zhuanhua(b);
  121.     int bFZ, bFM;
  122.     if (fuhao == "/") {
  123.         //除号需要倒置分子分母
  124.         bFZ = stoi(bs[1]);
  125.         bFM = stoi(bs[0]);
  126.     } else {
  127.         bFZ = stoi(bs[0]);
  128.         bFM = stoi(bs[1]);
  129.     }
  130.     //最小公约数
  131.     int yueshu, fenzi, fenmu;
  132.     if (fuhao == "*" || fuhao == "/") {
  133.         fenzi = aFZ * bFZ;
  134.         fenmu = aFM * bFM;
  135.     } else {
  136.         int gongbeishu = gongbeishu(aFM, bFM);
  137.         fenmu = gongbeishu;
  138.         aFZ = gongbeishu / aFM * aFZ;
  139.         bFZ = gongbeishu / bFM * bFZ;
  140.         if (fuhao == "+") {
  141.             fenzi = aFZ + bFZ;
  142.         } else {
  143.             fenzi = aFZ - bFZ;
  144.         }
  145.     }
  146.     if (fenzi == 0) {
  147.         return "0";
  148.     }
  149.     int max = max(abs(fenmu), abs(fenzi));
  150.     int min = min(abs(fenmu), abs(fenzi));
  151.     yueshu = zuixiaogongyueshu(max, min);
  152.     fenzi = fenzi / yueshu;
  153.     fenmu = fenmu / yueshu;
  154.     if (fenzi % fenmu == 0) {
  155.         return to_string(fenzi / fenmu);
  156.     } else {
  157.         if (fenmu < 0) {
  158.             //分母是负数，则需要将负号移到分子
  159.             fenmu = -fenmu;
  160.             fenzi = -fenzi;
  161.         }
  162.         return to_string(fenzi) + '/' + to_string(fenmu);
  163.     }
  164. }
  165.  
  166. string* zhuanhua(string shuzi) {
  167.     stringstream ss(shuzi);
  168.     string* shuzis = new string[2];
  169.     getline(ss, shuzis[0], '/');
  170.     if (ss.peek() != EOF) {
  171.         getline(ss, shuzis[1], '/');
  172.     } else {
  173.         shuzis[1] = "1";
  174.     }
  175.     return shuzis;
  176. }
  177.  
  178. int zuixiaogongyueshu(int a, int b) {
  179.     while (a % b != 0) {
  180.         b = a % b;
  181.     }
  182.     return b;
  183. }
  184.  
  185. int gongbeishu(int a, int b) {
  186.     int gongyueshu = zuixiaogongyueshu(a, b);
  187.     return a / gongyueshu * b / gongyueshu * gongyueshu;
  188. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/853980?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号