表达式计算器(数据结构)

伊海

要求：写一个控制台程序，该程序实现输入一个表达式能够根据表达式计算出相应的结果。
例如：例如：输入字符串"1+2*(3-4)/5="，输出结果：0.6
基本要求：能够对+ - * /  进行运算，能够对优先级进行运算和括号匹配运算。
扩展要求：
1.支持多数据类型输入，如: 0x12F（十六进制）、 12FH（十六进制）、  234O（八进制） 、‘F’（字符） 、0000 1111B（二进制）
2.支持未知数赋值运算  如： x=3  则  3X+5=14
3.支持常用函数运算 如： log、 ln、 sin、 sqrt等；
4.支持大数据计算；
5.支持自定义运算符。
这个题目涉及的东西很多很多，在往后待我慢慢给大家分析。
罗列下：
1.动态双向链表（这是我的算法，或许你可以试试数组，但是这两者的优劣在何处？我希望你能明白），表达式的校对
2.中缀表达式转化为后缀表达式
3.后缀表达式的计算
4.文件读写
5.不同进制的转换
6.大整数算法

（1）从大方向大致列举出这六点，现在我们就一项一项进行搞定。

1. 
   
2. //我们首先建立一个动态双向链表：
   
3. /* 建立一个头结点*/
   
4.       Formula_head = new node;
   
5.       init_node(Formula_head);
   
6.       Formula_head->ch = getchar();
   
7.       Formula_follow = Formula_head;
   
8. 
   
9. /* 从用户读取输入*/
   
10.         for(;;){
    
11.          
    
12.          newnode = new node;    /* 新增加一个节点来存储输入*/
    
13.          init_node(newnode);    /* 初始化节点数据 */
    
14.      
    
15.          while(1){    /* 获取输入数据，并且删除空格*/
    
16.          
    
17.        newnode->ch = getchar();
    
18.        //cin >> newnode->ch ;
    
19.           if(' ' != newnode->ch ){
    
20.            
    
21.            //print_link_data(Formula_follow);
    
22.            
    
23.            break;
    
24.            
    
25.           }
    
26.          }
    
27.      
    
28.          /* 结束输入*/
    
29.          if('\n' == newnode->ch){  
    
30.       
    
31.           break;
    
32.          
    
33.          }
    
34.    
    
35.          /* 加入节点*/
    
36.          Formula_follow = add_node(Formula_follow, newnode);
    
37.          
    
38.         }
    
39. 
    
40. //读取表达式之后，需要对表达式进行校对，处理未知数和防止输入不规则表达式（错误表达式）：
    
41.         /* 检查是否是未知数算式*/
    
42.         if( check_unknow(Formula_head) ){
    
43.          
    
44.          x_head = Formula_head;
    
45.          Formula_head = NULL;
    
46.          X_flag = 1;
    
47.          continue;
    
48.          
    
49.         }
    
50.    
    
51.         /*如果有未知数的处理*/
    
52.            if(X_flag){
    
53.             
    
54.          Formula_head = add_x_in_link(Formula_head,x_head);
    
55.          
    
56.         }
    
57.    
    
58.         /*检查错误*/
    
59.         if(check(Formula_head)){
    
60.          
    
61.          continue;
    
62.          
    
63.         }
    
64. 
    
65. /***************************************************
    
66. ** 函数名称：check
    
67. ** 函数功能：扫描链表,检查表达式是否错误
    
68. ** 入口参数：node *head
    
69. ** 出口参数：
    
70. ***************************************************/
    
71. int check(node *head)
    
72. {
    
73. int brackets = 0;
    
74. 
    
75. for(; head; head=head->next){
    
76.   
    
77.   /*连续出现2个运算符，报错*/
    
78.   if(('+'==head->ch) || ('-'==head->ch) ||
    
79.      ('*'==head->ch) || ('/'==head->ch)){
    
80.    
    
81.     if(('+'==head->next->ch) || ('-'==head->next->ch) ||
    
82.        ('*'==head->next->ch) || ('/'==head->next->ch)){
    
83.    
    
84.         cout<<"erro: Consecutive two operators!"<<endl;
    
85.    
    
86.         return 1;
    
87.        }
    
88.    
    
89.   }
    
90.   
    
91.   /* 括号不匹配，报错*/
    
92.   if('(' == head->ch){
    
93.    
    
94.    brackets++;
    
95.    
    
96.   }
    
97.   if(')' == head->ch){
    
98.    
    
99.    brackets--;
    
100.    
     
101.    if(brackets<0){
     
102.    
     
103.     cout<<"erro: brackets is not right,please check it out!"<<endl;
     
104.     return 1;
     
105.    
     
106.    }
     
107.   }
     
108.   
     
109. }
     
110. /* 括号不匹配*/
     
111. if(0 != brackets){
     
112.   
     
113.   cout<<"erro: brackets is not right,please check it out!"<<endl;
     
114.   return 1;
     
115.    
     
116. }
     
117. 
     
118. /*没错返回0*/
     
119. return 0 ;
     
120. 
     
121. }
     
122. 
     
123. /***************************************************
     
124. ** 函数名称：check_unknow
     
125. ** 函数功能：检查是否为未知数算式
     
126. ** 入口参数：node *head
     
127. ** 出口参数：
     
128. ***************************************************/
     
129. int check_unknow(node *head)
     
130. {
     
131. 
     
132. if(('x'==head->ch) && ('='==head->next->ch) && (NULL!=head->next->next)){
     
133.   
     
134.   return 1 ;
     
135.   
     
136. }
     
137. 
     
138. return 0;
     
139. }
     

复制代码

伊海

这里将数据结构真正用于实际项目中，达到算法最优、代码最优的效果。
（2）我们应该到了中缀表达式转化为后缀表达式。
这个数据结构在计算器表达式的项目中是非常经典的。这里我就再啰嗦几句，中缀表达式也叫做中缀记法，
如1+2*3便是，因为操作符在中间嘛，所以就叫做中缀表达式。
那么什么叫做后缀表达式，举一反三，即为操作数在后面嘛，那么即是：123*+。
后缀表达式也叫做逆波兰表达式。
中缀表达式转化为后缀表达式，栈的用武之地来了，说到栈，第一个词语就是FILO，
先进后出。中缀表达式转化为后缀表达式也正是用了这一个特点。

1. 
   
2. /***************************************************
   
3. ** 函数名称：*mid_to_bk
   
4. ** 函数功能：中缀转换成后缀表达式
   
5. ** 入口参数：node *head
   
6. ** 出口参数：
   
7. ***************************************************/
   
8. node *mid_to_bk(node *head)
   
9. {
   
10. node *mid = Separate_str(head); /* 处理后的中缀表达式链表*/
    
11. 
    
12. node *bk = NULL; /* 后缀表达式头指针*/
    
13. 
    
14. node *ptr = bk;
    
15. 
    
16. node *oper = NULL; /* 符号堆栈 */
    
17. 
    
18. node *newnode = NULL;
    
19. 
    
20. node *code_node = NULL; /* 用来记录，保存地址 */
    
21. 
    
22. /* 开始转换*/
    
23. for(; mid; mid=mid->next){
    
24. 
    
25. /* 将节点数据拷贝到新节点去*/
    
26. newnode = new node;
    
27. init_node(newnode);
    
28. copy_node_data(newnode,mid);
    
29. 
    
30. /* 如果遇到数字就直接入栈*/
    
31. if(NUM == newnode->type){
    
32. 
    
33. /*加入链表*/
    
34. if(NULL == bk){
    
35. ptr = bk = add_node(ptr,newnode);
    
36. } else{
    
37. ptr = add_node(ptr,newnode);
    
38. }
    
39. 
    
40. }
    
41. 
    
42. /* 如果遇到特殊表达式*/
    
43. else if(SP_OPERATOR == newnode->type){
    
44. 
    
45. /* 如果前一个运算符也是特殊运算符就要出栈 */
    
46. while(oper){
    
47. 
    
48. if(SP_OPERATOR == oper->type){
    
49. 
    
50. code_node = oper->befor; /* 将这个节点换到后缀表达式里面*/
    
51. ptr = add_node(ptr,oper);
    
52. oper = code_node;
    
53. 
    
54. } else break;
    
55. 
    
56. }
    
57. 
    
58. oper = add_node(oper,newnode);
    
59. 
    
60. }
    
61. 
    
62. 
    
63. /*如果遇到普通运算符*/
    
64. else if(OPERATOR == newnode->type){
    
65. 
    
66. /*'('直接进栈*/
    
67. if('(' == newnode->ch){
    
68. oper = add_node(oper,newnode);
    
69. }
    
70. 
    
71. /*')'直接退栈到')'*/
    
72. else if(')' == newnode->ch){
    
73. while(oper){
    
74. if('(' == oper->ch)break;/* 遇到'('退栈结束*/
    
75. code_node = oper->befor; /* 将这个节点换到后缀表达式里面*/
    
76. ptr = add_node(ptr,oper);
    
77. oper = code_node;
    
78. }
    
79. 
    
80. oper = del_node(oper); /* 删除掉'('符号*/
    
81. }
    
82. 
    
83. /* 遇到+-全部退栈，直到遇到'('，或者退完为止*/
    
84. else if(('+' == newnode->ch) || ('-' == newnode->ch)){
    
85. while(oper){
    
86. 
    
87. if('(' == oper->ch)break; /* 遇到'('退栈结束*/
    
88. code_node = oper->befor; /* 将这个节点换到后缀表达式里面*/
    
89. ptr = add_node(ptr,oper);
    
90. oper = code_node;
    
91. 
    
92. }
    
93. oper = add_node(oper,newnode);
    
94. }
    
95. 
    
96. /* 遇到/* 把特殊运算符全部退栈处理*/
    
97. else if(('*' == newnode->ch) || ('/' == newnode->ch)){
    
98. while(oper){
    
99. 
    
100. if('(' == oper->ch)break; /* 遇到'('和特殊运算符截止*/
     
101. if(('+' == oper->ch) || ('-' == oper->ch))break;
     
102. code_node = oper->befor; /* 将这个节点换到后缀表达式里面*/
     
103. ptr = add_node(ptr,oper);
     
104. oper = code_node;
     
105. 
     
106. }
     
107. oper = add_node(oper,newnode);
     
108. }
     
109. 
     
110. /*
     
111. * 下面这段程序是调试使用
     
112. */
     
113. #if 0
     
114. cout<<"mid: ";
     
115. print_link_data(test);
     
116. getchar();
     
117. #endif
     
118. 
     
119. }
     
120. 
     
121. }
     
122. 
     
123. 
     
124. /* 把最后留在堆栈里面的东西退出来*/
     
125. while(oper){
     
126. 
     
127. code_node = oper->befor; /* 将这个节点换到后缀表达式里面*/
     
128. ptr = add_node(ptr,oper);
     
129. oper = code_node;
     
130. 
     
131. }
     
132. 
     
133. 
     
134. ptr->next = NULL;
     
135. 
     
136. /*
     
137. * 下面这段程序是调试使用
     
138. */
     
139. #if 0
     
140. cout<<"mid: ";
     
141. print_link_data(bk);
     
142. #endif
     
143. 
     
144. return bk;
     
145. }
     
146. 
     

复制代码

伊海

（3）承接上，我们实现了中缀表达式转化为逆波兰表达式，这节，我们要做的肯定就是怎么样将逆波兰表达式计算出来。
其实这个计算过程是很简单了，如下：

1. /***************************************************
   
2. ** 函数名称：calculate
   
3. ** 函数功能：对后缀表达式进行计算处理
   
4. ** 入口参数：node *formula
   
5. ** 出口参数：result[0]
   
6. *******************************************
   
7. ********/
   
8. double calculate(node *formula)
   
9. {
   
10. 
    
11. double result[200];
    
12. int i=0;
    
13. for(; formula; formula = formula->next){
    
14. 
    
15. /*数据再次进堆栈*/
    
16. if(NUM == formula->type){
    
17. result = formula->num;
    
18. i++;
    
19. }
    
20. //由于前面进行了中缀表达式转化为逆波兰表达式，因此为这里的计算奠定了十足的运算基础。
    
21. /*遇到普通符号就直接进行判断并且计算*/
    
22. else if(OPERATOR == formula->type){
    
23. /*加法计算*/
    
24. if('+' == formula->ch){
    
25. i--;
    
26. result[i-1] = result[i-1]+result;
    
27. }
    
28. 
    
29. /*减法计算*/
    
30. if('-' == formula->ch){
    
31. i--;
    
32. result[i-1] = result[i-1]-result;
    
33. }
    
34. 
    
35. /*乘法计算*/
    
36. if('*' == formula->ch){
    
37. i--;
    
38. result[i-1] = result[i-1]*result;
    
39. }
    
40. 
    
41. /*除法计算*/
    
42. if('/' == formula->ch){
    
43. 
    
44. i--;
    
45. 
    
46. /* 如果除数是0的话提示错误*/
    
47. if(0 == result){
    
48. 
    
49. cout<<"erro: the divvisor equal zero!Please check is out!"<<endl;
    
50. exit(1);
    
51. 
    
52. } else{
    
53. result[i-1] = result[i-1]/result;
    
54. }
    
55. 
    
56. }
    
57. 
    
58. }
    
59. /*遇到特殊符号*/
    
60. else{
    
61. 
    
62. /*sin*/
    
63. if(!strcmp(formula->str,"sin")){ //进行符号匹配，如果是sin运算符，进行项目的运算。这里读者其实可以进行改进
    
64. result[i-1] = sin(result[i-1]);
    
65. }
    
66. 
    
67. /* cos*/
    
68. else if(!strcmp(formula->str,"cos")){
    
69. result[i-1] = cos(result[i-1]);
    
70. }
    
71. 
    
72. /* tan*/
    
73. else if(!strcmp(formula->str,"tan")){
    
74. result[i-1] = tan(result[i-1]);
    
75. }
    
76. 
    
77. /* log*/
    
78. else if(!strcmp(formula->str,"log")){
    
79. result[i-1] = log(result[i-1]);
    
80. }
    
81. 
    
82. /*sqrt*/
    
83. else if(!strcmp(formula->str,"sqrt")){
    
84. result[i-1] = sqrt(result[i-1]);
    
85. }
    
86. 
    
87. /*help*/
    
88. else if(!strcmp(formula->str,"help")){
    
89. 
    
90. r_file() ;
    
91. 
    
92. } else{
    
93. cout<<"have no this OPERATOR,if you want add it,please add it upon, thank you!\n"<<endl;
    
94. exit(1);
    
95. }
    
96. 
    
97. }
    
98. 
    
99. }
    
100. return result[0];
     
101. }

复制代码

//有些东西，看似很难，那是因为你没有突破心理的障碍，
//当你全身心投入去实践的时候，你会发现，一切都是那么简单并且有趣