中缀转后缀表达式并求值

通过栈将中缀表达式转换为后缀表达式并根据后缀表达式求解，包含的Header.h为之前发过的栈操作相关函数实例程序，改成头文件就行。练习+记录，高手无视。

OutPut:

The init formula:3+4*5+(6*7+8)*9
The stack is empty.
Convert result:345*+67*8+9*+
Calculate result:473

1. //Code by Pnig0s1992  
2. //Date:2012,3,21  
3. #include <stdio.h>  
4. #include <Windows.h>  
5. #include "Header.h"  
6.  
7. #define MAXLENGTH 50  
8.  
9. VOID ConvertAndCalc(LPSTR lpContainer,Stack S);  
10. int Caculate(LPSTR lpContainer,Stack S);  
11. int getOptPriv(CHAR cOpt);  
12.  
13. int main(int argc,char **argv)  
14. {  
15.     LPSTR lpContainer = "3+4*5+(6*7+8)*9";  
16.     Stack myStack = CreateStack();  
17.     printf("\nThe init formula:%s",lpContainer);  
18.     ConvertAndCalc(lpContainer,myStack);  
19.     system("pause");  
20.     return 0;  
21. }  
22.  
23. int getOptPriv(CHAR cOpt)  
24. {  
25.     switch(cOpt)  
26.     {  
27.     case '(':  
28.         return 7;  
29.     case ')':  
30.         return 7;  
31.     case '*':  
32.         return 5;  
33.     case '/':  
34.         return 5;  
35.     case '+':  
36.         return 3;  
37.     case '-':  
38.         return 3;  
39.     default:  
40.         return 0;  
41.     }  
42. }  
43.  
44. VOID ConvertAndCalc(LPSTR lpContainer,Stack S)  
45. {  
46.     LPSTR lpResult = (LPSTR)HeapAlloc(GetProcessHeap(),HEAP_ZERO_MEMORY,MAXLENGTH);  
47.     LPSTR lpTemp = (LPSTR)HeapAlloc(GetProcessHeap(),HEAP_ZERO_MEMORY,MAXLENGTH);  
48.     while(*lpContainer != '\0')  
49.     {  
50.         if(isalnum(*lpContainer))  
51.         {  
52.             sprintf(lpTemp,"%c",*lpContainer);  
53.             strcat(lpResult,lpTemp);  
54.             ZeroMemory(lpTemp,MAXLENGTH);  
55.         }else 
56.         {  
57.             if(isEmpty(S))  
58.             {  
59.                 Push(*lpContainer,S);  
60.             }else if (*lpContainer == ')')  
61.             {  
62.                 while(!isEmpty(S) && getTop(S) != '(')  
63.                 {  
64.                     sprintf(lpTemp,"%c",Pop(S));  
65.                     strcat(lpResult,lpTemp);  
66.                     ZeroMemory(lpTemp,MAXLENGTH);  
67.                 }  
68.                 Pop(S);  
69.             }else 
70.             {  
71.                 if(getOptPriv(getTop(S)) < getOptPriv(*lpContainer))  
72.                 {  
73.                     Push(*lpContainer,S);  
74.                 }else 
75.                 {  
76.                     while((!isEmpty(S)) && (getOptPriv(getTop(S)) >= getOptPriv(*lpContainer)) && getTop(S) != '(')  
77.                     {  
78.                         sprintf(lpTemp,"%c",Pop(S));  
79.                         strcat(lpResult,lpTemp);  
80.                         ZeroMemory(lpTemp,MAXLENGTH);  
81.                     }  
82.                     Push(*lpContainer,S);  
83.                 }  
84.             }  
85.         }  
86.         lpContainer++;  
87.     }  
88.     while(!isEmpty(S))  
89.     {  
90.         sprintf(lpTemp,"%c",Pop(S));  
91.         strcat(lpResult,lpTemp);  
92.         ZeroMemory(lpTemp,MAXLENGTH);  
93.     }  
94.     MakeEmpty(S);  
95.     printf("\nConvert result:%s",lpResult);  
96.     int iResult = Caculate(lpResult,S);  
97.     printf("\nCalculate result:%d",iResult);  
98.     return;  
99. }  
100.  
101. int Caculate(LPSTR lpContainer,Stack S)  
102. {  
103.     int iTemp;  
104.     int iResult;  
105.     while(*lpContainer != '\0')  
106.     {  
107.         if(isdigit(*lpContainer))  
108.         {  
109.             LPSTR lpTemo = (LPSTR)HeapAlloc(GetProcessHeap(),HEAP_ZERO_MEMORY,MAXLENGTH);  
110.             sprintf(lpTemo,"%c",*lpContainer);  
111.             Push(atoi((const char *)lpTemo),S);  
112.         }else 
113.         {  
114.             switch(*lpContainer)  
115.             {  
116.             case '+':  
117.                 Push(Pop(S)+Pop(S),S);  
118.                 break;  
119.             case '-':  
120.                 Push(Pop(S)-Pop(S),S);  
121.                 break;  
122.             case '*':  
123.                 Push(Pop(S)*Pop(S),S);  
124.                 break;  
125.             case '/':  
126.                 Push(Pop(S)/Pop(S),S);  
127.                 break;  
128.             default:  
129.                 break;  
130.             }  
131.         }  
132.         lpContainer++;  
133.     }  
134.     return Pop(S);  
135. } 

本文转hackfreer51CTO博客，原文链接：http://blog.51cto.com/pnig0s1992/812563，如需转载请自行联系原作者