堆栈应用：表达式求值（C语言）

堆栈应用：表达式求值（C语言）

两个定义

• 中缀表达式：运算符号位于两个运算数之间。如：a + b * c - d / e
• 后缀表达式：运算符号位于两个运算数之后。如：a b c * + d e / -

大致过程

1. 用后缀表达式求值：
   对于后缀表达式，可以比较容易处理。大致过程为：将后缀表达式从左到右扫描，遇到数字就将数字压如堆栈中，遇到运算符就将运算符前面的两个数字出栈，将运算符置于两数字之间运算，将运算结果入栈。最后栈中剩余的最后一个元素就是运算结果。

   • 【例子】求：6 2 / 3 - 4 2 * +

     步骤：

     1. 从左到右扫描，遇到6和2，分别将其压进堆栈中。
        
     2. 遇到除号，将6和2出栈，计算6/2=3，将3入栈；继续扫描，后面遇见一个3，继续入栈。
        
     3. 遇到减号，将两个3出栈，计算3-3=0，将0入栈；继续扫描，后面遇见4与2，将其入栈。
        
     4. 遇到乘号，将4和2出栈，计算4*2=8，将8入栈；
        
     5. 遇到加号，将0和8出栈，计算0+8=8，将8入栈，扫描之后发现已经没有字符，而堆栈中只有8这个元素，故结果为8。
        

2. 将中缀表达式转换为后缀表达式
   所以现在我们要做的就是将中缀表达式变成后缀表达式。观察两种表达式的转换：2 + 9 / 3 - / 5 —> 2 9 3 / + 5 -

   1. 运算数相对顺序不变
   2. 运算符号顺序发生改变
      • 需要存储“等待中”得运算符号
      • 要将当前运算符号与“等待中”的运算符号比较

   中缀表达式转换为后缀表达式的过程：

   • 从头到尾读取中缀表达式的每个对象，对不同的对象按照不同的情况处理。

     1. 运算符：直接输出；
     2. 左括号：压入堆栈；
     3. 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）；
     4. 运算符：
        • 若优先级大于栈顶运算符时，则把它压入栈中；
        • 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；在比较新的栈顶元素运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压入栈中。
     5. 若各对象处理完毕，则将堆栈中存留的运算符一并输出。

     

具体代码

1. main.c

   #include<stdio.h>
   #include<stdlib.h>
   #include"Expression_evaluation.h"
   
   int main(void)
   {
       char InfixStr[MAXSIZE] = { 0 }, SuffixStr[MAXSIZE] = { 0 };
       Read_Expression(InfixStr,MAXSIZE);//将在键盘上输入的中缀表达式保存在字符串InfixStr中
       //puts(InfixStr);
       InfixToSuffix(InfixStr, SuffixStr,MAXSIZE);//将中缀表达式抓换成后缀表达式
       //puts(SuffixStr);
       printf("\n结果是：%f\n", Calculate(SuffixStr, MAXSIZE));
   
       system("pause");
       return 0;
   }
   

2. Expression_evaluation.h

   #define MAXSIZE 100
   
   //存放字符的堆栈
   struct SNode {
       char Data[MAXSIZE];
       int Top;
   };
   typedef struct SNode* Stack;
   
   //存放浮点数的堆栈
   struct SNodeOfInt {
       float Data[MAXSIZE];
       int Top;
   };
   typedef struct SNodeOfInt* StackOfFloat;
   
   int Compare(char, Stack);//在中后缀表达式转换的时候，加减乘除号比较优先级，判断加减乘除号是否入栈
   void Read_Expression(char[], int);//读取键盘输入的表达式
   void InfixToSuffix(char[], char[], int);//将中缀表达式转换为后缀表达式
   float Calculate(char[], int);//由后缀表达式求出表达式结果
   
   //入栈
   void Push(Stack, char);
   void PushFloat(StackOfFloat, float);
   
   //出栈
   char Pop(Stack);
   float PopFloat(StackOfFloat);
   

3. Read_Expression.c

   #include<stdio.h>
   #include<stdlib.h>
   #include"Expression_evaluation.h"
   
   
   void Read_Expression(char str[], int length)
   {
       printf("请输入所需求值的中缀表达式（英文输入法）：\n");
       gets(str);
   
       return str;
   }
   

4. InfixToSuffix.c

   #include<stdio.h>
   #include<stdlib.h>
   #include"Expression_evaluation.h"
   
   void InfixToSuffix(char Infix[], char Suffix[], int length)
   {
       int i = 0,j=0,Tag=0;
       //建立一个空栈
       struct SNode S_1 = { {'\0'},-1 };
       Stack SPtr = &S_1;
   
       //扫描中缀表达式的所有字符，根据字符的值做出不同操作
       while (Infix[i] != '\0')
       {
           //当扫描到数字的时候，直接输出到字符串Suffix中
           if (Infix[i] <= '9'&&Infix[i] >= '0')
           {
               Suffix[j] = Infix[i];
               j++;
           }
           //当扫描到空格的时候，直接输出到字符串Suffix中
           else if (Infix[i] == ' ')
           {
               Suffix[j] = Infix[i];
               j++;
           }
           //当扫描到加减乘除运算符的时候，将其与堆栈顶元素比较优先级，根据优先级决定进栈还是栈顶元素出栈输出
           else if (Infix[i] == '+' || Infix[i] == '-' || Infix[i] == '*' || Infix[i] == '/')
           {
               Suffix[j] =' ';
               j++;
               //当栈顶元素出栈输出时，扫描到的元素要继续与新的栈顶元素比较优先级，直至扫描到的元素入栈
               Tag = 0;
               while (Tag == 0)
               {
                   Tag = Compare(Infix[i], SPtr);
                   if (Tag == 0)
                   {
                       Suffix[j] = Pop(SPtr);
                       j++;
                   }
                   else
                   {
                       Push(SPtr, Infix[i]);
                   }
               }
           }
           //如果扫描到左括号，直接进栈
           else if(Infix[i]=='(')
           {
               Push(SPtr, Infix[i]);
           }
           //如果扫描到右括号，一直出栈输出直到栈顶元素是左括号，然后将栈顶的左括号出栈但不输出
           else if (Infix[i] == ')')
           {
               Suffix[j] = ' ';
               j++;
               while (SPtr->Data[SPtr->Top] != '(')
               {
                   Suffix[j] = Pop(SPtr);
                   j++;
               }
               Pop(SPtr);
           }
           i++;
       }
       //扫描完之后将堆栈中所有元素出栈
       while (SPtr->Top != -1)
       {
           Suffix[j] = Pop(SPtr);
           j++;
       }
   }
   

5. Compare.c

   #include<stdio.h>
   #include<stdlib.h>
   #include"Expression_evaluation.h"
   
   int Compare(char ch_1, Stack SPtr)
   {
       //如果堆栈空，将扫描到的运算符号进栈
       if (SPtr->Top == -1)
       {
           return 1;
       }
       //当栈顶是左括号时，将扫描到的运算符号进栈
       if (SPtr->Data[SPtr->Top] == '(')
       {
           return 1;
       }
       //当栈顶是乘号或者除号的情况
       else if (SPtr->Data[SPtr->Top] == '/' || SPtr->Data[SPtr->Top] == '*')
       {
           //如果扫描到的也是乘号或除号，将栈顶元素出栈
           if (ch_1 == '*' || ch_1 == '/')
           {
               return 0;
           }
           //如果扫描到的是加号或者减号，将栈顶元素出栈
           else
           {
               return 0;
           }
       }
       //当栈顶元素是加号或者减号时
       else
       {
           //如果扫描到的也是乘号或除号，将栈顶元素进栈
           if (ch_1 == '*' || ch_1 == '/')
           {
               return 1;
           }
           //如果扫描到的是加号或者减号，将栈顶元素出栈
           else
           {
               return 0;
           }
       }
   }
   

6. Calculate.c

   #include<stdio.h>
   #include<stdlib.h>
   #include"Expression_evaluation.h"
   
   float Calculate(char Suffix[], int length)
   {
       float sum = 0, temp = 0, first = 0, last = 0;
       int i = 0;
       //建立一个空栈
       struct SNodeOfInt S = { {0},-1 };
       StackOfFloat SPtr = &S;
       while (Suffix[i] != '\0')
       {
           //扫描后缀表达式，计算结果
           while (Suffix[i] != '\0')
           {
               //当扫描到的是数字字符，将其转换成数字，并将其压入栈中
               if (Suffix[i] <= '9'&&Suffix[i] >= '0')
               {
                   sum = 0;
                   while (Suffix[i] <= '9'&&Suffix[i] >= '0')
                   {
                       temp = (float)(Suffix[i] - '0');
                       sum = sum * 10 + temp;
                       i++;
                   }
                   PushFloat(SPtr, sum);
               }
   
               //当扫描到空格，忽略
               if (Suffix[i] == ' ')
               {
                   i++;
               }
               //当扫描到加减乘除号，将栈顶两个元素弹出，并将其用扫描到的运算符号计算，将结果压入栈中
               if (Suffix[i] == '+' || Suffix[i] == '-' || Suffix[i] == '*' || Suffix[i] == '/')
               {
                   last = PopFloat(SPtr);
                   first = PopFloat(SPtr);
                   if (Suffix[i] == '+')
                   {
                       PushFloat(SPtr, first + last);
                       i++;
                   }
                   else if (Suffix[i] == '-')
                   {
                       PushFloat(SPtr, first - last);
                       i++;
                   }
                   else if (Suffix[i] == '*')
                   {
                       PushFloat(SPtr, first*last);
                       i++;
                   }
                   else
                   {
                       PushFloat(SPtr, first / last);
                       i++;
                   }
               }
   
           }
           return PopFloat(SPtr);//栈中最后一个数字就是结果，将其返回
       }
   
   }
   

7. Pop.c

   #include<stdio.h>
   #include<stdlib.h>
   #include"Expression_evaluation.h"
   
   char Pop(Stack SPtr)
   {
       if (SPtr->Top == -1)
       {
           printf("堆栈空");
           return '\n';//栈空时返回回车键
       }
       else
       {
           return (SPtr->Data[(SPtr->Top)--]);//先返回栈顶元素，再将Top减一。
       }
   }
   
   float PopFloat(StackOfFloat SPtr)
   {
       if (SPtr->Top == -1)
       {
           printf("堆栈空");
           return '\n';//栈空时返回回车键
       }
       else
       {
           return (SPtr->Data[(SPtr->Top)--]);//先返回栈顶元素，再将Top减一。
       }
   }
   

8. Push.c

   #include<stdio.h>
   #include<stdlib.h>
   #include"Expression_evaluation.h"
   
   void Push(Stack SPtr, char itme)
   {
       if (SPtr->Top == MAXSIZE - 1)
       {
           printf("堆栈满");
           return;
       }
       else
       {
           SPtr->Data[++(SPtr->Top)] = itme;//Top先自加一，然后再给栈顶元素赋值。
           return;
       }
   }
   
   void PushFloat(StackOfFloat SPtr, float itme)
   {
       if (SPtr->Top == MAXSIZE - 1)
       {
           printf("堆栈满");
           return;
       }
       else
       {
           SPtr->Data[++(SPtr->Top)] = itme;//Top先自加一，然后再给栈顶元素赋值。
           return;
       }
   }