[关闭]
@zsh-o 2018-08-26T23:00:37.000000Z 字数 6824 阅读 1067

计算字符串表达式的值（正则表达式 | 后缀表达式）

算法

如题，写了两个，一个是用python正则表达式，另一个C++用后缀表达式

Python正则表达式

思路是用正则表达式搜索所有的可计算的表达式，用结果替换，然后迭代计算得到最终结果

  1. #!/usr/bin/env python
  2. # -*- coding: utf-8 -*-
  4. # Time      : 2018/3/21 9:24
  5. # Author    : zsh_o
  7. import re
  9. def cal_mul(matched):
  10.     sa = matched.group(1)
  11.     sb = matched.group(2)
  12.     if len(sa)>1 and sa[0] == '0' and sa[1] == '0':
  13.         a = -float(sa)
  14.     else:
  15.         a = float(sa)
  16.     if len(sb)>1 and sb[0] == '0' and sb[1] == '0':
  17.         b = -float(sb)
  18.     else:
  19.         b = float(sb)
  20.     c = a * b
  21.     if c < 0:
  22.         return '00' + str(-c)
  23.     else:
  24.         return str(c)
  25. def cal_div(matched):
  26.     sa = matched.group(1)
  27.     sb = matched.group(2)
  28.     if len(sa) > 1 and sa[0] == '0' and sa[1] == '0':
  29.         a = -float(sa)
  30.     else:
  31.         a = float(sa)
  32.     if len(sb) > 1 and sb[0] == '0' and sb[1] == '0':
  33.         b = -float(sb)
  34.     else:
  35.         b = float(sb)
  36.     c = a / b
  37.     if c < 0:
  38.         return '00' + str(-c)
  39.     else:
  40.         return str(c)
  41. def cal_add(matched):
  42.     sa = matched.group(1)
  43.     sb = matched.group(2)
  44.     if len(sa) > 1 and sa[0] == '0' and sa[1] == '0':
  45.         a = -float(sa)
  46.     else:
  47.         a = float(sa)
  48.     if len(sb) > 1 and sb[0] == '0' and sb[1] == '0':
  49.         b = -float(sb)
  50.     else:
  51.         b = float(sb)
  52.     c = a + b
  53.     if c < 0:
  54.         return '00' + str(-c)
  55.     else:
  56.         return str(c)
  57. def cal_sub(matched):
  58.     sa = matched.group(1)
  59.     if sa == '':
  60.         sa = '0'
  61.     sb = matched.group(2)
  62.     if len(sa) > 1 and sa[0] == '0' and sa[1] == '0':
  63.         a = -float(sa)
  64.     else:
  65.         a = float(sa)
  66.     if len(sb) > 1 and sb[0] == '0' and sb[1] == '0':
  67.         b = -float(sb)
  68.     else:
  69.         b = float(sb)
  70.     c = a - b
  71.     if c < 0:
  72.         return '00' + str(-c)
  73.     else:
  74.         return str(c)
  77. def cal_bracket(matched):
  78.     bracket_s = matched.group(1)
  79.     p = bracket_s
  80.     ## 先算除法
  81.     st = []
  82.     while st is not None:
  83.         st = re.search('([0-9]+[.]{0,1}[0-9]*)\/([0-9]+[.]{0,1}[0-9]*)', p)
  84.         p = re.sub('([0-9]+[.]{0,1}[0-9]*)\/([0-9]+[.]{0,1}[0-9]*)', cal_div, p, count=1)
  85.     st = []
  86.     while st is not None:
  87.         st = re.search('([0-9]+[.]{0,1}[0-9]*)\*([0-9]+[.]{0,1}[0-9]*)', p)
  88.         p = re.sub('([0-9]+[.]{0,1}[0-9]*)\*([0-9]+[.]{0,1}[0-9]*)', cal_mul, p, count=1)
  89.     ## 先算负的，再算正的，防止开头是负号的情况
  90.     st = []
  91.     while st is not None:
  92.         st = re.search('([0-9]*[.]{0,1}[0-9]*)\-([0-9]+[.]{0,1}[0-9]*)', p)
  93.         p = re.sub('([0-9]*[.]{0,1}[0-9]*)\-([0-9]+[.]{0,1}[0-9]*)', cal_sub, p, count=1)
  94.     st = []
  95.     while st is not None:
  96.         st = re.search('([0-9]+[.]{0,1}[0-9]*)\+([0-9]+[.]{0,1}[0-9]*)', p)
  97.         p = re.sub('([0-9]+[.]{0,1}[0-9]*)\+([0-9]+[.]{0,1}[0-9]*)', cal_add, p, count=1)
  98.     st = p[1:-1]
  99.     return st
  101. s = '1-2*((60-30+(9-2*5/3+7/3*99/4*2998+10*2998+10*568/14))-(-4*3)/(16-3*2))'
  102. # s = '1-2'
  103. p = s
  104. st = []
  105. while st is not None:
  106.     st = re.search('(\([^\(\)]+\))', p)
  107.     p = re.sub('(\([^\(\)]+\))', cal_bracket, p)
  109. def cal_final(final_s):
  110.     p = final_s
  111.     st = []
  112.     while st is not None:
  113.         st = re.search('([0-9]+[.]{0,1}[0-9]*)\/([0-9]+[.]{0,1}[0-9]*)', p)
  114.         p = re.sub('([0-9]+[.]{0,1}[0-9]*)\/([0-9]+[.]{0,1}[0-9]+)', cal_div, p, count=1)
  115.     st = []
  116.     while st is not None:
  117.         st = re.search('([0-9]+[.]{0,1}[0-9]*)\*([0-9]+[.]{0,1}[0-9]*)', p)
  118.         p = re.sub('([0-9]+[.]{0,1}[0-9]*)\*([0-9]+[.]{0,1}[0-9]*)', cal_mul, p, count=1)
  119.     ## 先算负的，再算正的，防止开头是负号的情况
  120.     st = []
  121.     while st is not None:
  122.         st = re.search('([0-9]*[.]{0,1}[0-9]*)\-([0-9]+[.]{0,1}[0-9]*)', p)
  123.         p = re.sub('([0-9]*[.]{0,1}[0-9]*)\-([0-9]+[.]{0,1}[0-9]*)', cal_sub, p, count=1)
  124.     st = []
  125.     while st is not None:
  126.         st = re.search('([0-9]+[.]{0,1}[0-9]*)\+([0-9]+[.]{0,1}[0-9]*)', p)
  127.         p = re.sub('([0-9]+[.]{0,1}[0-9]*)\+([0-9]+[.]{0,1}[0-9]*)', cal_add, p, count=1)
  128.     a = float(p)
  129.     if len(p) > 1 and p[0] == '0' and p[1] == '0':
  130.         a = -a
  131.     return a
  132. print(cal_final(p))
  133. print(eval(s))

C++后缀表达式

支持小数

  1. //
  2. // Created by zsh96 on 2018/4/20.
  3. //
  4. /**
  5.  * 计算字符串的值，后缀表达式
  6.  * */
  8. #include <iostream>
  9. #include <cstring>
  10. #include <map>
  11. #include <vector>
  12. #include <stack>
  14. using namespace std;
  16. struct Item{
  17.     bool isNumber;
  18.     char symbol;
  19.     double value;
  20.     Item(double value):isNumber(true),value(value){}
  21.     Item(char symbol):isNumber(false),symbol(symbol){}
  22. };
  24. class Operator{
  25. public:
  26.     char label;
  27.     explicit Operator(char label): label(label){}
  28.     virtual double calculate(double a, double b)=0;
  29. };
  30. class Add:public Operator{
  31. public:
  32.     Add() : Operator('+') {}
  33.     double calculate(double a, double b) override {
  34.         return a + b;
  35.     }
  36. };
  37. class Sub:public Operator{
  38. public:
  39.     Sub() : Operator('-') {}
  40.     double calculate(double a, double b) override {
  41.         return a - b;
  42.     }
  43. };
  44. class Mul:public Operator{
  45. public:
  46.     Mul() : Operator('*') {}
  47.     double calculate(double a, double b) override {
  48.         return a * b;
  49.     }
  50. };
  51. class Div:public Operator{
  52. public:
  53.     Div() : Operator('/') {}
  54.     double calculate(double a, double b) override {
  55.         return a / b;
  56.     }
  57. };
  59. class OperatorManager{
  60. public:
  61.     map<char, Operator *> operatorList;
  62.     map<char, int> operatorLevel;
  63.     OperatorManager(){
  64.         operatorList['+'] = new Add();
  65.         operatorList['-'] = new Sub();
  66.         operatorList['*'] = new Mul();
  67.         operatorList['/'] = new Div();
  69.         operatorLevel['+'] = 1;
  70.         operatorLevel['-'] = 1;
  71.         operatorLevel['*'] = 2;
  72.         operatorLevel['/'] = 2;
  73.         operatorLevel['('] = 3;
  74.         operatorLevel[')'] = 3;
  75.     }
  76.     double calculate(char operc, double a, double b){
  77.         return operatorList[operc]->calculate(a, b);
  78.     }
  79. };
  81. bool isNumber(char c){
  82.     return c>='0' && c<='9';
  83. }
  84. double e10(int n){
  85.     double res = 10;
  86.     while(--n){
  87.         res *= 10;
  88.     }
  89.     return res;
  90. }
  91. OperatorManager operatorManager;
  92. int main(){
  93.     cout<<"Inputs: ";
  94.     string line;
  95.     getline(cin, line);
  97.     vector<Item *> Items;
  98.     double sum = 0;
  99.     bool isfloat = false;
  100.     bool isnegative = false;
  101.     char LastC = '~';
  102.     int floatNum = 0;
  103.     bool lastisNumber = (line[0]!='(');
  104.     for(int i=0; i<line.size(); i++){
  105.         char c = line[i];
  106.         if(!isNumber(c)){
  107.             if(c == '-' && (LastC == '(' || LastC == '~')){
  108.                 Items.push_back(new Item(0.));
  109.             }
  110.             if(c=='.'){
  111.                 if(isfloat){
  112.                     cout<<"Error"<<endl;
  113.                 }else{
  114.                     isfloat = true;
  115.                 }
  116.                 lastisNumber = true;
  117.             }else{
  118.                 if(c == ' '){
  119.                     continue;
  120.                 }
  121.                 if(lastisNumber){
  122.                     Items.push_back(new Item(sum));
  123.                 }
  124.                 Items.push_back(new Item(c));
  125.                 sum = 0;
  126.                 floatNum = 0;
  127.                 isfloat = false;
  128.                 lastisNumber = false;
  129.                 LastC = c;
  130.             }
  131.         }else {
  132.             double t = c - '0';
  133.             if (!isfloat) {
  134.                 sum = sum * 10 + t;
  135.             } else {
  136.                 floatNum++;
  137.                 sum = sum + (c - '0') / e10(floatNum);
  138.             }
  139.             lastisNumber = true;
  140.             if (i == line.size() - 1) {
  141.                 Items.push_back(new Item(sum));
  142.             }
  143.             LastC = c;
  144.         }
  145.     }
  147.     // 转为后缀表达式
  148.     vector<Item *> postfix;
  149.     stack<Item *> temp_stack;
  151.     for(int i=0; i<Items.size(); i++){
  152.         Item *item = Items[i];
  153.         if(item->isNumber){
  154.             postfix.push_back(item);
  155.         }else{
  156.             if(item->symbol=='('){
  157.                 temp_stack.push(item);
  158.             }else if(item->symbol==')'){
  159.                 Item *temp = temp_stack.top();
  160.                 while(!temp_stack.empty() && temp->symbol!='('){
  161.                     postfix.push_back(temp);
  162.                     temp_stack.pop();
  163.                     if(!temp_stack.empty())
  164.                         temp = temp_stack.top();
  165.                 }
  166.                 temp_stack.pop();
  167.             }else{
  168.                 if(!temp_stack.empty()){
  169.                     Item *temp = temp_stack.top();
  170.                     while(!temp_stack.empty() && operatorManager.operatorLevel[temp->symbol]>=operatorManager.operatorLevel[item->symbol] && temp->symbol!='('){
  171.                         postfix.push_back(temp);
  172.                         temp_stack.pop();
  173.                         if(!temp_stack.empty())
  174.                             temp = temp_stack.top();
  175.                     }
  176.                 }
  177.                 temp_stack.push(item);
  178.             }
  179.         }
  180.     }
  181.     while(!temp_stack.empty()){
  182.         postfix.push_back(temp_stack.top());
  183.         temp_stack.pop();
  184.     }
  186.     // ------
  187.     cout<<"Items: ";
  188.     for(int i=0; i<Items.size(); i++){
  189.         Item *item = Items[i];
  190.         if(item->isNumber){
  191.             cout<<item->value;
  192.         }else{
  193.             cout<<item->symbol;
  194.         }
  195.     }
  196.     cout<<endl;
  197.     cout<<"Postfix Expression: ";
  198.     for(int i=0; i<postfix.size(); i++){
  199.         Item *item = postfix[i];
  200.         if(item->isNumber){
  201.             cout<<item->value;
  202.         }else{
  203.             cout<<item->symbol;
  204.         }
  205.     }
  206.     cout<<endl;
  208.     // 计算
  209.     for(int i=0; i<postfix.size(); i++){
  210.         Item *item = postfix[i];
  211.         if(item->isNumber){
  212.             temp_stack.push(item);
  213.         }else{
  214.             Item *b = temp_stack.top();
  215.             temp_stack.pop();
  216.             Item *a = temp_stack.top();
  217.             temp_stack.pop();
  218.             temp_stack.push(new Item(operatorManager.calculate(item->symbol, a->value, b->value)));
  219.         }
  220.     }
  221.     // -----
  222.     Item *result = temp_stack.top();
  223.     printf("Result: %.3lf\n", result->value);
  224.     cin.get();
  225. }
  1. Inputs: 1-2*((60-30+(9-2*5/3+7/3*99/4*2998+10*2998+10*568/14))-(-4*3)/(16-3*2))
  2. Items: 1-2*((60-30+(9-2*5/3+7/3*99/4*2998+10*2998+10*568/14))-(0-4*3)/(16-3*2))
  3. Postfix Expression: 126030-925*3/-73/99*4/2998*+102998*+10568*14/++043*-1632*-/-*-
  4. Result: -407113.162
  6. Inputs: 1.4*(2-4.5/5) - (-3.2+5)
  7. Items: 1.4*(2-4.5/5)-(0-3.2+5)
  8. Postfix Expression: 1.424.55/-*03.2-5+-
  9. Result: -0.260
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注