Facebook(1) : 简单的计算程序

回复 20# wwwyhx
对，上面15楼提到这个问题，后来也提到通过加参数来解决。
隔了这么长时间回头之前的代码还是有很多不理想的地方。现在稍做改动再贴一下，不知还有没有别的问题，供参考。

1. 
   
2. #include <iostream>
   
3. #include <cstdio>
   
4. using namespace std;
   
5. char c;
   
6. char get()
   
7. {
   
8.         while((c = cin.get()) == ' ');
   
9.         return c;
   
10. }
    
11. double num()
    
12. {
    
13.         double ret = 0, dec = 0.1;
    
14.         int f = 1;
    
15.         if((c = get()) == '-') f = -1;
    
16.         else cin.putback(c);
    
17.         while(c = get()) {
    
18.                 if(c >= '0' && c <= '9')
    
19.                         ret = ret * 10 + c - '0';
    
20.                 else break;
    
21.         }
    
22.         if(c != '.') return ret * f;
    
23.         while(c = get()) {
    
24.                 if(c >= '0' && c <= '9') {
    
25.                         ret += dec * (c - '0');
    
26.                         dec /= 10;
    
27.                 }
    
28.                 else break;
    
29.         }
    
30.         return ret * f;
    
31. }
    
32. double calc_add(double, int);
    
33. double calc_mul(double a, int op)
    
34. {
    
35.         double ret;
    
36.         c = get();
    
37.         if(c == '(') {
    
38.                 ret = calc_add(0, 1);
    
39.                 c=get();
    
40.         } else {
    
41.                 cin.putback(c);
    
42.                 ret = num();
    
43.         }
    
44.         ret = (op ? a * ret : a / ret);
    
45.         if(c == '*' || c == '/')
    
46.                 return calc_mul(ret, (c == '*' ? 1 : 0));
    
47.         return ret;
    
48. }
    
49. double calc_add(double a, int op)
    
50. {
    
51.         double ret = calc_mul(1, 1);
    
52.         ret = (op ? a + ret : a - ret);
    
53.         if(c == '+' || c == '-')
    
54.                 return calc_add(ret, (c == '+' ? 1 : 0));
    
55.         return ret;
    
56. }
    
57. int main()
    
58. {
    
59.         cout << calc_add(0, 1) << endl;
    
60.         return 0;
    
61. }
    

复制代码

回复  wwwyhx
对，上面15楼提到这个问题，后来也提到通过加参数来解决。
隔了这么长时间回头之前的代码还是有很多不理想的地方。现在稍做改动再贴一下，不知还有没有别的问题，供参考。
darksteel 发表于 2012-4-11 07:15

    其实是编译原理的一个递归下降语法分析, 可以用在稍稍复杂的情况, 列出语法规则直接写程序, 左结合不需要参数可以用迭代的办法实现,比如下面这个:

1. 
   
2. //implement like a+b*(2-c)
   
3. 
   
4. //Top down parser, the correct expression is the first step
   
5. //add = mul [+ or - mul]*
   
6. //mul = factor [* or / factor]*
   
7. //factor = numeric or (add) or (+ or - factor)
   
8. 
   
9. //notice: use reference for all parameter
   
10. int add(const char*& p);
    
11. int mul(const char*& p);
    
12. int factor(const char*& p);
    
13. int numeric(const char*& p);
    
14. 
    
15. void skipblank(const char*& p)
    
16. {
    
17.         while (*p == ' ')
    
18.                 p++;
    
19. }
    
20. 
    
21. int add(const char*& p)
    
22. {
    
23.         skipblank(p);
    
24. 
    
25.         int nRet = mul(p);
    
26.         skipblank(p);
    
27. 
    
28.         while (*p == '+' || *p == '-')
    
29.         {
    
30.                 if (*p == '+')
    
31.                         nRet += mul(++p); //should be ++p not p++, otherwise, compile error
    
32.                 else nRet -= mul(++p);
    
33.                 skipblank(p);
    
34.         }
    
35. 
    
36.         return nRet;
    
37. }
    
38. 
    
39. int mul(const char*& p)
    
40. {
    
41.         skipblank(p);
    
42. 
    
43.         int nRet = factor(p);
    
44.         skipblank(p);
    
45. 
    
46.         //you can't use recursion like "* or / mul" here, if will calculate from the right.
    
47.         //E.g consider 2*3/4, if recursive method like "* or / mul" is used, it will calculate
    
48.         //"3/4" first which result is 0, and then calculate 2*0 == 0. However, it should be
    
49.         //2*3 first == 6 and then 6/4 which is 1
    
50.         while (*p == '*' || *p == '/')
    
51.         {
    
52.                 if (*p == '*')
    
53.                         nRet *= factor(++p);
    
54.                 else nRet /= factor(++p);
    
55.                 skipblank(p);
    
56.         }
    
57. 
    
58.         return nRet;
    
59. }
    
60. 
    
61. int factor(const char*& p)
    
62. {
    
63.         skipblank(p);
    
64. 
    
65.         int nRet = 0;
    
66.         if (*p == '(')
    
67.         {
    
68.                 p++;
    
69.                 nRet = add(p);
    
70.                 skipblank(p);
    
71.                 if (*p == ')')
    
72.                         p++;
    
73.         }
    
74.         else if (*p == '+' || *p == '-')
    
75.         {
    
76.                 bool bNeg = *p == '-';
    
77.                 p++;
    
78.                 nRet = factor(p);
    
79.                 if (bNeg) nRet = -nRet;
    
80.         }
    
81.         else
    
82.                 nRet = numeric(p);
    
83. 
    
84.         return nRet;
    
85. }
    
86. 
    
87. int numeric(const char*& p)
    
88. {
    
89.         skipblank(p);
    
90. 
    
91.         int nRet = 0;
    
92.         while (*p >= '0' && *p <= '9')
    
93.         {
    
94.                 nRet = (*p - '0') + nRet * 10;
    
95.                 p++;
    
96.         }
    
97. 
    
98.         return nRet;
    
99. }
    

复制代码

半个小时写了一把，基本case都ok（如果发现什么case不行请拍砖），等会儿再爬楼看各位前辈的讨论～

1. #include <iostream>
   
2. #include <cstdlib>
   
3. #include <stack>
   
4. 
   
5. using namespace std;
   
6. 
   
7. bool priority_equal_higher(char stop, char newop) {
   
8.         if (stop == '*' || stop == '/') return true;
   
9.         else if (newop == '+' || newop == '-') return true;
   
10.         else return false;
    
11. }
    
12. 
    
13. int calc(char op, int op1, int op2) {
    
14.         if (op == '*') return op1 * op2;
    
15.         else if (op == '/') return op1 / op2;
    
16.         else if (op == '+') return op1 + op2;
    
17.         else return op1 - op2;
    
18. }
    
19. 
    
20. int main() {
    
21.         string input;
    
22.         cout << "please input an expression: ";
    
23.         cin >> input;
    
24.         cout << "your input: " << input << endl;
    
25. 
    
26.         stack<int> operands;
    
27.         stack<char> operators;
    
28.         for (int i = 0; i < input.size();) {
    
29.                 if (input[i] >= '0' && input[i] <= '9') {
    
30.                         int start = i++;
    
31.                         while (i < input.size() && (input[i] >= '0' && input[i] <= '9'))
    
32.                                 ++i;
    
33.                         operands.push(atoi(input.substr(start, i - start).c_str()));
    
34.                 } else {
    
35.                         while (operators.empty() == false
    
36.                                 && priority_equal_higher(operators.top(), input[i]) == true) {
    
37.                                 int op1 = operands.top();
    
38.                                 operands.pop();
    
39.                                 int op2 = operands.top();
    
40.                                 operands.pop();
    
41.                                 char op = operators.top();
    
42.                                 operators.pop();
    
43.                                 int res = calc(op, op2, op1);
    
44.                                 operands.push(res);
    
45.                         }
    
46.                         operators.push(input[i++]);
    
47.                 }
    
48.         }
    
49.         while (operators.empty() == false) {
    
50.                 int op1 = operands.top();
    
51.                 operands.pop();
    
52.                 int op2 = operands.top();
    
53.                 operands.pop();
    
54.                 char op = operators.top();
    
55.                 operators.pop();
    
56.                 int res = calc(op, op2, op1);
    
57.                 operands.push(res);
    
58.         }
    
59.         cout << "res: " << operands.top() << endl;
    
60.         operands.pop() ;
    
61.         return 0;
    
62. }

复制代码

回复 22# wwwyhx
嗯，这种跟文法有点相关的都可以这么递归的调来调去。以前做题的时候看见有些人能直接写成迭代的形式，应该得想的比较清楚才行，因为递归总是更容易想一些。
大体方法有了结合性就好解决了，你这个也是一种办法

这题好像可以转成前缀表达式，然后慢慢搞就行了

弱弱地传个代码，最傻的办法，一步步算。。。（java）
对了，这里的code不支持java吗？

1. import java.util.LinkedList;
   
2. import java.util.regex.Matcher;
   
3. import java.util.regex.Pattern;
   
4. 
   
5. public class Arithmetic{
   
6. public static void main(String[] args){
   
7.   String input = new String("1- 2*3+ 6/3");
   
8.   System.out.println(arith(input));
   
9. }
   
10. 
    
11. private static int arith(String input){
    
12.   String str = input.replaceAll("\\s+", "");
    
13.   String[] dataStrList = str.split("[\\+\\-\\*\\/]");
    
14.   LinkedList<Integer> dataLink = new LinkedList<Integer>();
    
15.   for (String tempStr : dataStrList){
    
16.    dataLink.add(Integer.valueOf(tempStr));
    
17.   }
    
18.   
    
19.   String[] signStrList = str.split("\\d+");
    
20.   StringBuffer signs = new StringBuffer();
    
21.   for (String signStr : signStrList){
    
22.    signs.append(signStr);
    
23.   }
    
24.   
    
25.   Pattern p = Pattern.compile("[\\*\\/]");
    
26.   Matcher m = p.matcher(signs);
    
27.   while (m.find()){
    
28.    if (signs.charAt(m.start()) == '*'){
    
29.     dataLink.add(m.start(),
    
30.       dataLink.get(m.start()) * dataLink.get(m.start() + 1));
    
31.    }else{
    
32.     dataLink.add(m.start(),
    
33.       dataLink.get(m.start()) / dataLink.get(m.start() + 1));
    
34.    }
    
35.    signs.deleteCharAt(m.start());
    
36.    dataLink.remove(m.start() + 1);
    
37.    dataLink.remove(m.start() + 1);
    
38.    m = p.matcher(signs);
    
39.   }
    
40.   
    
41.   int result = dataLink.get(0);
    
42.   for (int i = 0; i < signs.length(); i++){
    
43.    int sg = 1;
    
44.    if (signs.charAt(i) == '-') {
    
45.     sg = -1;
    
46.    }
    
47.    result += sg * dataLink.get(i + 1);
    
48.   }
    
49.   
    
50.   return result;
    
51. }
    
52. }
    
53. 
    
54. 
    

复制代码