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

计算字符串表达式的值(正则表达式 | 后缀表达式)

算法


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

Python正则表达式

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

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

C++后缀表达式

支持小数

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

  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
  5. Inputs: 1.4*(2-4.5/5) - (-3.2+5)
  6. Items: 1.4*(2-4.5/5)-(0-3.2+5)
  7. Postfix Expression: 1.424.55/-*03.2-5+-
  8. Result: -0.260
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注