用栈实现表达式计算.docx

设计思想算法一：利用栈将中缀表达式转化成后缀表达式再进行计算 1）构造 char 类型的栈函数以及栈的相关函数（出栈函数、 进栈函数、创建栈 函数、销毁栈函数、判断栈是否为空函数、看栈顶函数等） 2）在 main 函数中让用户进行输入，将用户输入的字符串进行循环、 判断（如果数字字符后面的是运算符，则在数字字符后加“ #”以便进行区分；否则，继续循环并将判断后的字符串传递到新的数组中， 循环结束后， 再将数组 传递给中缀表达式转后缀表达式函数（ Min_Back（） ） 3）中缀表达式转后缀表达式函数是利用运算符的优先级进行判断来将中缀表 达式转换成后缀表达式的函数函数中利用构建的栈以及栈的相关函数对运 算符进行操作： 先看栈顶， 如果栈为空或栈顶元素为 ‘（'或者栈顶元素为 ‘ +' 或‘—'并且现有运算符为‘ *'、‘/ '或‘ %'又或是现有运算符为‘ （'，则 现有元素进栈；否则，再对现有元素进行判断：如果现有元素为‘） '，运算 符出栈直到 ‘（' 出栈；否则，运算符出栈直到栈空或者栈顶元素的优先级低 于现有运算符，现有运算符才进栈循环结束后，将栈中的运算符全部依次 输出，最后将后缀表达式传递给求值函数（ countfor（） ），再销毁栈。

4）求值函数中首先是利用 strtod（） 函数将数字字符串转换成 double 类型的 数字，然后构建一个数字栈，将转换后的数字传递到栈中，每当遇到运算符 时，就从数字栈中“扔出”两个数字进行相应的运算，循环结束后，将数字 栈中的数字“扔出” ，并输出成为表达式最终的结果算法二：利用创建的两个栈直接对表达式进行计算 1）分别构建一个 char 类型和一个 double 类型的栈函数以及栈的相关函数 （出 栈函数、进栈函数、创建栈函数、销毁栈函数、判断栈是否为空函数、看栈 顶函数等）判断(如2)在 main 函数中让用户进行输入，将用户输入的字符串进行循环、果数字字符后面的是运算符，则在数字字符后加“ #”以便进行区分；否则，继续循环)并将判断后的字符串传递到新的数组中， 循环结束后， 再将数组 传递给中缀表达式转后缀表达式函数( Countfor () ) 3)在 Countfor() 函数中先创建一个数字栈和一个符号栈， 对表达式进行循环， 直到元素为' \0 '在循环中如果元素为数字、 点或者 #，将元素赋给新的数 组 Consist[] ，再判断下一个元素是否为 #，若是则利用 strtod() 函数将数组 中的字符串转换成 double 类型的数字， 然后数字进栈， 清空数组 Consist[] ； 否则，继续判断。

若元素不为数字、点或者 #，则先看栈顶，如果栈为空或栈顶元素为‘('或者栈顶元素为‘ +'或‘—'并且现有元素为‘ *'、‘/ '或 ‘ %'又或是现有元素为‘ ('，则现有元素进栈；否则，再对现有元素进行判 断：如果现有元素为‘) '，运算符出栈直到‘ ('出栈；否则，运算符出栈直 到栈空或者栈顶元素的优先级低于现有运算符，现有运算符才进栈每当有 一个运算符出栈， 就从数栈中取两个数与运算符一起传递给 Judge() 函数, 并 将函数的返回值压入栈中循环结束后，将栈中的运算符全部依次输出，每 当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给 Judge() 函 数, 并将函数的返回值压入栈中， 最后输出数字栈中的数字成为表达式的最终 结果，再销毁栈 4) Judge() 函数是利用 switch 语句对传入进来的运算符进行判断，并将传入 的两个数进行相应的运算，并返回运算结果二、算法流程图算法一：利用栈将中缀表达式转化成后缀表达式再进行计算图 1 为算法一中 main() 函数的算法流程图，主要功能为：录入字符串和区分数字字 符与运算符字符图1中缀转后缀表达式算法main()函数流程图图2为算法一中Mid_Back()函数的算法流程图，主要功能为：将中缀表达式转换 成后缀表达式。

图 2 中缀转后缀表达式算法 Mid_Back() 函数流程图图 3 为算法countfor() 函数的算法流程图，主要功能为：根据后缀表达式求出表达式的值图3中缀转后缀表达式算法 countfor()函数流程图算法二：利用两个栈(数字栈和符号栈)直接对表达式求值图4为算法二中main()函数的算法流程图，主要功能为：录入字符串和区分数字字符与运算符字符图4表达式直接求值算法 main()函数流程图图5为算法二中 Countfor ()函数的算法流程图，主要功能为：利用两个栈直接对表达式进行取值计算图5表达式直接求值算法 Countfor ()函数流程图图6为算法二中Judge()函数的算法流程图，主要功能为：判断运算符并根据判断将 两个数进行相应的计算，返回计算结果图6表达式直接求值算法 Judge()函数流程图三、源代码下面给出的是用一个栈对表达式中缀转后缀再进行运算的算法实现的程序的源代码:#include ""#include ""#include ""#include ""#define STACK_INIT_SIZE 10 )||a[i]=='#'){||Ba_str[i]=='#'){ )||Min_str[i]==#){//判断Min_str[i] 是否为数字或者点、#，Consist[j]=Min_str[i];// 是，则传入 Consist[] 数组，直至 Min_str[i] 为#j++；i++;if(Min_str[i]=='#') // 如果 Min_str[i] 为 #{double 类eod=strtod(Consist,NULL);// 利用 strtod 函数，将 Consist[] 数组中的字符串转换成 型的数字Push(Od,eod); //eod 进栈for(j=0;j<20;j++)// 将 Consist[] 数组循环清空{Consist[j]='\0';}j=0;}else --i;}else{//Min_str[i] 是运算符GetTop(Op,eop); // 看栈if(StackEmpty(Op)||eop=='('||((eop=='+'||eop=='-')&&(Min_str[i]=='*'||Min_str[i]=将栈中已有的运算符与现有的运算符进行比较='%'||Min_str[i]=='/'))|| Min_str[i]=='('){ Push(Op,Min_str[i]);} //else{if(Min_str[i]==')') //如果现有的运算符为 ')'Od#=eod;{Pop(Op,eop); // 则栈中的运算符出栈，for(;eop!='(';) // 直到出栈的运算符为 '('{Pop(Od,eod); //一个运算符出栈，数栈中就 Pop 出两个数，进行运算Pop(Od,eod);Od1=eod;eod=Judge(eop,Od1,Od2);// 对运算符进行判断，并根据判断进行运算Push(Od,eod); // 将函数的返回值压入进栈Pop(Op,eop);}}else{Pop(Op,eop); // 运算符出栈Pop(Od,eod);// 一个运算符出栈，数栈中就 Pop 出两个数，进行运算Od2=eod;Pop(Od,eod);Od1=eod;eod=Judge(eop,Od1,Od2); // 对运算符进行判断，并根据判断进行运算Push(Od,eod); // 将函数的返回值压入进栈GetTop(Op,eop); // 看栈顶 if(StackEmpty(Op)||eop=='('||((eop=='+'||eop=='-')&&(Min_str[i]=='*'||Min_str[i]=='%'||Min_str[i]=='/'))||Min_str[i]=='('){ Push(Op,Min_str[i]);}else{Pop(Op,eop); // 运算符出栈Pop(Od,eod);// 一个运算符出栈，数栈中就 Pop 出两个数，进行运算Od2=eod;Pop(Od,eod);Od#=eod;Push(Od,eod); //将函数的返回值压入进栈Push(Op,Min_str[i]);}}}}}for(;!StackEmpty(Op); //运算符出栈，直到栈空{Pop(Op,eop); // 运算符出栈Pop(Od,eod); // 一个运算符出栈，数栈中就 Pop 出两个数，进行运算Od2=eod;Pop(Od,eod);Od1=eod;eod=Judge(eop,Od1,Od2); // 对运算符进行判断，并根据判断进行运算Push(Od,eod); // 将函数的返回值压入进栈}Pop(Od,eod);printf("=%f",eod); //输出表达式最终结果DestroyStack(Od); //销毁数字栈 OdDestroyStack(Op); //销毁字符栈 Op}double Judge(char c_Operator,double Od1,double Od2){switch(c_Operator) //判断 c_Operator 是什么运算符，并根据判断进行运算运算符为减号，则两数相减运算符为加号，则两数相加运算符为乘号，则两数相乘运算符为除号，则两数相除case '-':{eod=Od1-Od2; break;}//case '+':{eod=Od1+Od2; break;}//case '*':{eod=Od1*Od2; break;} //case 7':{eod=Od1/Od2;break;} //运算符为取余号，则两数相除取余case '%':{eod=(int)Od1%(int)Od2;break;} //// degault:}return eod; // 返回运算结果}四、运行结果算法一：利用栈将中缀表达式转化成后缀表达式再进行计算。

将表达式“ +2*( 32-54/9 ) -7%5+3=”录入，先将中缀表达式转化成后缀表达式,#是为了区分数字与符号，得到结果为“ 56.400000 ”，为正确结果图7中缀表达式转化成后缀表达式再进行计算算法的运行结果图算法利用创建的两个栈直接对表达式进行计算将表达式“ +2* (32-54/9 ) -7%5+3=”录入，得到结果为“ 5。