本文主要是介绍将浮点型算式的中缀表达式转换成后缀表达式并算出式子结果,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
最近因为需要了解如何将在Win应用程序控制台输入的算式表达式转化成其后缀表达式的算法,所以在网上搜索了一下,看到许多人的程序都只是对应于运算数在0~9的范围内的整型运算式,所以自己就写了一个可以计算浮点型算式的程序,一下是运行时的截图:
式子中的a,b,c是可供用户自行输入的变量。
首先,我先对输入的运算符进行了简单的合法性判断,我的判断代 码如下:
//函数的传入参数为一个字符型数组,该数组存放的是用户输入的表达式,还有一个引用传递的数组下标值
bool IsValid(char exp[],int& position){bool flag=false;for(position;position<100;position++){if(exp[position]=='\0'){if(!(exp[0]=='(')&&!isdigit(exp[0])&&!(exp[0]=='a')&&!(exp[0]=='b')&&!(exp[0]=='c')){ //判断表达式是否以+,-,*,/等运算符开头,如是,则表达式不合格cout<<"the expression can not end of operator"<<endl;return false;}if(!(exp[position-1]==')')&&!isdigit(exp[position-1])&&!(exp[position-1]=='a')&&!(exp[position-1]=='c')&&!(exp[position-1]=='b')){cout<<"the expression can not end of operator"<<endl; //判断表达式是否以+,-,*,/等运算符结尾,如是,则表达式不合格return false;}break;}else{if (!isdigit(exp[position])){if (exp[position]=='('){operatorstack.push(exp[position]);}else{if(exp[position]==')'){if (operatorstack.empty()){cout<<"the expression is unvalid!"<<endl; //若表达式有多余的"(",")",则不合格return false;}else{operatorstack.pop();}}else{if (exp[position]=='a'||exp[position]=='b'||exp[position]=='c'){continue;}if(exp[position-1]=='+'||exp[position-1]=='-'||exp[position-1]=='*'||exp[position-1]=='^'||exp[position-1]=='/'||exp[position-1]=='%'||exp[position-1]=='&'||exp[position-1]=='|'||exp[position-1]=='>'||exp[position-1]=='<'){cout<<"the expression can not contain two continuous operators"<<endl; //若表达式中有两个以上的+,-,*,/等运算符出现,则不合格return false;}continue;}}}}}cout<<"the expression is valid!"<<endl;return true;
}
上面我给出的例子的判断合法性输出为:
初步判断完算式的合法性之后,就进行后缀表达式的输出,我的程序思想是取决于我式子存放的数据类型的,我是将算式存放在一个char型的数组内,所以在输出后缀表达式的时候我就利用了这个存放格式的特点,我的函数In2Pos(char exp[],int& position ,char* tmp)有三个参数,第一个为存放算式的数组,第二个为引用参数,作为数组开始检查的其实位置,第三个参数为存放后缀表达式的char数组:
1,首先,判断是否为算式末尾的回车换行符'\0',若是,则说明已经到了算式的结尾,将操作符栈的操作符都存放到后缀表达式的数组中,退出程序,否则进行下面的判断,
2,判断当前字符是否为数字,或小数点,或用户赋值的变量a,b,,c,若是则存放到后缀表达式的数组中,若不是这进行第3步判断
3,栈为空时,遇到运算符,直接入栈
4,遇到左括号:将其入栈
5,遇到右括号:执行出栈操作,并将出栈的元素存放到后缀表达式的数组中,直到弹出栈的是左括号,左括号不存放到后缀表达式 的数组中。
6,遇到其他运算符:加减乘除等,弹出所有优先级大于或者等于该运算符的栈顶元素,并将出栈的元素存放到后缀表达式的数组 中,然后将该运算符入栈
7,最后回到第1步
一下是我的代码实现:
void In2Pos(char exp[],int& position ,char* tmp){int i=0,j;for (j=0;j<100;j++){tmp[j]='e';}stack<char> ope;for (position;position<100;position++){if (exp[position]=='\0'){while (!ope.empty()){char exchange;exchange=ope.top();ope.pop();tmp[i++]=exchange;}return ;}else{if (isdigit(exp[position])||exp[position]=='.'||exp[position]=='a'||exp[position]=='b'||exp[position]=='c'){tmp[i++]=exp[position];}else{if (ope.empty()){ope.push(exp[position]);}else{if (judge(ope.top(),exp[position])){while (!ope.empty()&&judge(ope.top(),exp[position])){if (exp[position]==')'){while(ope.top()!='('){tmp[i++]=ope.top();ope.pop();}ope.pop();break;}else{tmp[i++]=ope.top();ope.pop();}}if (exp[position]!=')'){ope.push(exp[position]);}}else{ope.push(exp[position]);}}}}}return ;
}
接下来就是计算算式的值了,我的思想是:
1,首先,判断是否为算式末尾的回车换行符'\0',若是,则说明已经到了算式的结尾,则将结果sum返回,如不是则接下去判断,
2,先判断字符是否为数字,若是,则不断地从该字符往后检测是否为数字知道遇到下一个运算符,期间将数字的整数部分和小数部分计算出来,然后相加起来,压入数字栈中,如果不是数字则接下去判断,
3,如果是用户赋值的变量,则将对应的数值压入数字栈中,
4,若是运算符,运算符栈为空时,遇到运算符,直接入栈
5,遇到左括号:将其入栈
6,遇到右括号:执行出栈操作,并将出栈的元素输出赋值给operator1,然后弹出数字栈的两个数值进行运算,在将运算结果压入数字栈,然后循环,直到弹出栈的是左括号,左括号直接弹出。
7,遇到其他运算符:加减乘除:弹出所有优先级大于或者等于该运算符的栈顶元素,并将出栈的元素输出赋值给operator1,然后弹出数字栈的两个数值进行运算,在将运算结果压入数字栈,然后将该运算符入栈
8,最后到了结尾,返回1
计算程序的代码为:
float Evaluate(char exp[],int& position){int j;float sum=0,tmp1=0,tmp2=0,tmp3=0;float firstnum,lastnum;char operator1;stack<float> num; <span style="white-space:pre"> </span>//数字栈stack<char> ope;<span style="white-space:pre"> </span>//运算符栈while(true){if (exp[position]=='\0'){while (!ope.empty()){operator1=ope.top();ope.pop();lastnum=num.top();num.pop();firstnum=num.top();num.pop();tmp3=count(firstnum,lastnum,operator1);num.push(tmp3);}sum=num.top();return sum;}else{if (isdigit(exp[position])||exp[position]=='.'){while (isdigit(exp[position])||exp[position]=='.'){if (exp[position]=='.'){position++;int point=0;float pnum=0;while(isdigit(exp[position])){point++;pnum=(float)(exp[position]-48);for (j=0;j<point;j++){pnum=pnum/10;}tmp2+=pnum;position++;}}else{tmp1=tmp1*10+(int)(exp[position]-48);position++;}}tmp1=tmp1+tmp2;num.push(tmp1);tmp1=0;tmp2=0;}else if(exp[position]=='a'){num.push(a);position++;}else if(exp[position]=='b'){num.push(b);position++;}else if(exp[position]=='c'){num.push(c);position++;}else{if (ope.empty()){ope.push(exp[position]);position++;}else{if (judge(ope.top(),exp[position])){while (!ope.empty()&&judge(ope.top(),exp[position])){//cout<<"end"<<endl;if (exp[position]==')'){while(ope.top()!='('){// tmp[i++]=ope.top();operator1=ope.top();lastnum=num.top();num.pop();firstnum=num.top();num.pop();tmp3=count(firstnum,lastnum,operator1);ope.pop();num.push(tmp3);}ope.pop();//cout<<"end"<<endl;break;}else{// tmp[i++]=ope.top();operator1=ope.top();lastnum=num.top();num.pop();firstnum=num.top();num.pop();tmp3=count(firstnum,lastnum,operator1);ope.pop();num.push(tmp3);}}if (exp[position]!=')'){ope.push(exp[position]);}position++;}else{ope.push(exp[position]);position++;}}}}}return sum;
}
以下是main函数:
<span style="font-size:14px;">// Expression.cpp : 定义控制台应用程序的入口点。
//#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <cassert>
#include <math.h>
#include<stack>
using namespace std;float a,b,c;<span style="white-space:pre"> </span>//全局变量a,b,cbool IsValid(char exp[],int& position){bool flag=false;for(position;position<100;position++){if(exp[position]=='\0'){if(!(exp[0]=='(')&&!isdigit(exp[0])&&!(exp[0]=='a')&&!(exp[0]=='b')&&!(exp[0]=='c')){ //判断表达式是否以+,-,*,/等运算符开头,如是,则表达式不合格cout<<"the expression can not end of operator"<<endl;return false;}if(!(exp[position-1]==')')&&!isdigit(exp[position-1])&&!(exp[position-1]=='a')&&!(exp[position-1]=='c')&&!(exp[position-1]=='b')){cout<<"the expression can not end of operator"<<endl; //判断表达式是否以+,-,*,/等运算符结尾,如是,则表达式不合格return false;}break;}else{if (!isdigit(exp[position])){if (exp[position]=='('){operatorstack.push(exp[position]);}else{if(exp[position]==')'){if (operatorstack.empty()){cout<<"the expression is unvalid!"<<endl; //若表达式有多余的"(",")",则不合格return false;}else{operatorstack.pop();}}else{if (exp[position]=='a'||exp[position]=='b'||exp[position]=='c'){continue;}if(exp[position-1]=='+'||exp[position-1]=='-'||exp[position-1]=='*'||exp[position-1]=='^'||exp[position-1]=='/'||exp[position-1]=='%'||exp[position-1]=='&'||exp[position-1]=='|'||exp[position-1]=='>'||exp[position-1]=='<'){cout<<"the expression can not contain two continuous operators"<<endl; //若表达式中有两个以上的+,-,*,/等运算符出现,则不合格return false;}continue;}}}}}cout<<"the expression is valid!"<<endl;return true;
}int judge(char op1,char op2){if (op2=='('){return 0;}if (op2==')'){return 1;}if (op2=='+'||op2=='-'){switch (op1){case '+':case '-':case '(':return 0;break;case '*':case '/':case '^':return 1;break;}}if (op2=='*'||op2=='/'){switch (op1){case '+':case '-':case '(':case '*':case '/':return 0;break;case '^':return 1;break;}}if (op2=='^'){switch (op1){case '+':case '-':case '(':case '*':case '/':case '^':return 0;break;}}
}void In2Pos(char exp[],int& position ,char* tmp){int i=0,j;for (j=0;j<100;j++){tmp[j]='e';}stack<char> ope;for (position;position<100;position++){if (exp[position]=='\0'){while (!ope.empty()){char exchange;exchange=ope.top();ope.pop();tmp[i++]=exchange;}return ;}else{if (isdigit(exp[position])||exp[position]=='.'||exp[position]=='a'||exp[position]=='b'||exp[position]=='c'){tmp[i++]=exp[position];}else{if (ope.empty()){ope.push(exp[position]);}else{if (judge(ope.top(),exp[position])){while (!ope.empty()&&judge(ope.top(),exp[position])){//cout<<"end"<<endl;if (exp[position]==')'){while(ope.top()!='('){tmp[i++]=ope.top();ope.pop();}ope.pop();//cout<<"end"<<endl;break;}else{tmp[i++]=ope.top();ope.pop();}}if (exp[position]!=')'){ope.push(exp[position]);}}else{ope.push(exp[position]);}}}}}return ;
}float count(float first,float last,char ope){float cot;switch (ope){case '+':cot=first+last;break;case '-':cot=first-last;break;case '*':cot=first*last;break;case '/':cot=first/last;break;case '^':cot=pow(first,last);break;}return cot;
}
float Evaluate(char exp[],int& position){int j;float sum=0,tmp1=0,tmp2=0,tmp3=0;float firstnum,lastnum;char operator1;stack<float> num;stack<char> ope;while(true){if (exp[position]=='\0'){while (!ope.empty()){operator1=ope.top();ope.pop();lastnum=num.top();num.pop();firstnum=num.top();num.pop();tmp3=count(firstnum,lastnum,operator1);num.push(tmp3);}sum=num.top();return sum;}else{if (isdigit(exp[position])||exp[position]=='.'){while (isdigit(exp[position])||exp[position]=='.'){if (exp[position]=='.'){position++;int point=0;float pnum=0;while(isdigit(exp[position])){point++;pnum=(float)(exp[position]-48);for (j=0;j<point;j++){pnum=pnum/10;}tmp2+=pnum;position++;}}else{tmp1=tmp1*10+(int)(exp[position]-48);position++;}}tmp1=tmp1+tmp2;num.push(tmp1);tmp1=0;tmp2=0;}else if(exp[position]=='a'){num.push(a);position++;}else if(exp[position]=='b'){num.push(b);position++;}else if(exp[position]=='c'){num.push(c);position++;}else{if (ope.empty()){ope.push(exp[position]);position++;}else{if (judge(ope.top(),exp[position])){while (!ope.empty()&&judge(ope.top(),exp[position])){//cout<<"end"<<endl;if (exp[position]==')'){while(ope.top()!='('){// tmp[i++]=ope.top();operator1=ope.top();lastnum=num.top();num.pop();firstnum=num.top();num.pop();tmp3=count(firstnum,lastnum,operator1);ope.pop();num.push(tmp3);}ope.pop();//cout<<"end"<<endl;break;}else{// tmp[i++]=ope.top();operator1=ope.top();lastnum=num.top();num.pop();firstnum=num.top();num.pop();tmp3=count(firstnum,lastnum,operator1);ope.pop();num.push(tmp3);}}if (exp[position]!=')'){ope.push(exp[position]);}position++;}else{ope.push(exp[position]);position++;}}}}}return sum;
}int main(){cout<<"My procedure can calculate integer type and float-point type equation."<<endl;cout<<"welcome to operate my procedure."<<endl;cout<<"please input the value of a,b,c:"<<endl;cin>>a>>b>>c;cout<<"your input is \na="<<a<<"\nb="<<b<<"\nc="<<c<<endl;cin.ignore();int position=0;char expression[100];cout<<"please input your expression"<<endl;cin.getline(expression,100);IsValid(expression,position);cout<<endl;position=0;char t[100];In2Pos(expression,position,t);cout<<"the postfix expression of this expression is:"<<endl;int i=0;while(t[i]!='e'){cout<<(char)t[i];i++;}cout<<endl;cout<<endl;position=0;cout<<"the answer of the expression is :"<<endl;cout<<Evaluate(expression,position)<<endl;cout<<endl;cout<<"thanks for operating my procedure."<<endl;return 0;}
</span>
这篇关于将浮点型算式的中缀表达式转换成后缀表达式并算出式子结果的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!