这是我们C++的一个小小的课程设计;
因为时间比较短,支持的运算符就只有“+”,“-”,“x”,"/","%","#"(幂)。
核心部分推荐参考:
https://baike.baidu.com/item/%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F/6160580?fr=aladdin
主要是看懂中缀表达式转换为后缀表达式的规则,以及后缀表达式(逆波兰式)的计算方法,其他的就简单了。
主流程:
后缀表达式计算方法:
推荐使用链栈结构,自行百度,我这里纯粹使用了一个结构体,但是整体上也是拿这个当做栈那样用,具体的,看代码吧:
#include<iostream>
#include<stack>
#include<string>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<windows.h>
using namespace std;
typedef long long ll;
struct mix{
char Oper; //运算符
double num; //数字
int sign; //标记,存数字用num,标记为1,存运算符用Oper,标记为2
};
mix nifix[10000000]; //储存中缀表达式
int q=0; //记录nifix数组大小
string a; //读入字符串
stack<char> tool; //保存运算符
vector<mix> suffix; //保存后缀表达式
int priority(char s){ //给操作符赋予优先级
switch (s){
case '(':return 0; //这里是为了方便操作括号,实际上"()"优先级大
case '+':
case '-':
return 1;
case '*':
case '/':
case '%':
return 2;
case '#':return 3;
}
}
double calcu(double a,double b,char s){
switch (s){
case '+' : return a+b;
case '-' : return a-b;
case '*' : return a*b;
case '/' : return a/b;
case '%' : return (ll)a%(ll)b;
//一开始用的强转int,double转int存在误差,所以换成了long long
case '#' : return pow(a,b);
}
}
bool judge(string s){ //判断表达式是否合法
int n=s.length();
bool f=false;
stack<char> t;
for(int i=0;i<n;i++){
if(!(a[i]>='0'&&a[i]<='9')){
if(a[i]!='+'&&a[i]!='-'&&a[i]!='*'&&a[i]!='/'&&
a[i]!='#'&&a[i]!='.'&&a[i]!='%'&&a[i]!='('&&a[i]!=')'){
f=true;
break;
}
} //有非法标识符,直接标记f为true并退出循环
if(s.substr(i,2)=="/0"){
f=true; //每次截取长度为2的子串
break; //0不能做除数
}
if(t.empty()&&a[i]==')'){
f=true;
break;
}
if((s[n-1]<'0'||s[n-1]>'9')&&s[n-1]!=')'){
f=true; //表达式最后一位不是数字或者')'的不合法
break;
}
if(a[i]=='('){
t.push(a[i]); //左括号入栈
}
if(a[i]==')'){ //每有一个右括号,弹出一个左括号
t.pop();
}
}
if(t.empty()&&!f){ //括号匹配(栈空)并且符合其他条件,表达式合法
return true;
}
return false;
}
string dealneg(string str){ //处理字符串里的负数 ,补0.
for(int i=0;i<str.length();i++){
if(str[i]=='-'){
if(i==0){
str.insert(0,1,'0'); //表达式第一位,为'-',如-3+(5*(3-7))这类的
} //在每一个'-'前面补上一个'0'
else if(str[i-1]=='('){ //表达式中间出现负数,该负数前面必然有左括号;
str.insert(i,1,'0'); //在i处的前面加一个0 变成0-n;
} //如:3+(-3*5) 或者 3+(-3*(-3))
}
}
return str;
}
void strtonif(string a){ //字符串转化为中缀表达式
int n=a.length();
// int q=0;
for(int i=0;i<n;){
if(a[i]>='0'&&a[i]<='9'||a[i]=='.'){
string temp="";
int l=i;
while(a[l]>='0'&&a[l]<='9'||a[l]=='.'){ //实数用一个string保存,
temp+=a[l];
//不直接用char数组,是因为操作的对象长度未知,char数组大小不好确定
l++;
}
temp+='\0';
int y=temp.length(); //string 转 字符数组
char ss[y];
for(int z=0;z<y;z++){
ss[z]=temp[z];
}
nifix[q].num =atof(ss); //字符串转实数函数
nifix[q].sign=1;
q++;
i=l; //注意移动坐标i;
}
else{
nifix[q].Oper=a[i]; //运算符就直接存
nifix[q].sign=2;
q++;
i++;
}
}
}
void niftosuf(){ //中缀表达式转后缀表达式
int cut;
for(int i=0;i<q;i++){ //预处理,为了方便进行运算符优先级的比较,先往栈里压入一个运算符
if(nifix[i].sign==1){
suffix.push_back(nifix[i]); //数字直接存进后缀表达式
}
if(nifix[i].sign ==2){
tool.push(nifix[i].Oper);
cut=i+1;
break; //保证stack有东西,先存一个运算符
}
}
mix r; //中间变量
for(int i=cut;i<q;i++){ //从那个运算符之后再操作
if(nifix[i].sign==1){
suffix.push_back(nifix[i]);
}
else if(nifix[i].sign==2){
if(nifix[i].Oper==')'){ //假如是右括号,就去往前匹配一个左括号
while(tool.top()!='('){ //没匹配到之前,运算符存到后缀表达式
r.Oper =tool.top();
r.sign =2;
suffix.push_back(r);
tool.pop(); //弹出运算符
}
tool.pop(); //弹出左括号
}
else if((tool.empty())||
priority(nifix[i].Oper)>priority(tool.top())){ //这里要注意判断栈是不是空
tool.push(nifix[i].Oper); //运算符优先级大于栈顶元素,入栈
}
else if(nifix[i].Oper=='('){
tool.push('('); //左括号入栈
}
else if((tool.empty())||priority(nifix[i].Oper)<=priority(tool.top())){
int y=priority(nifix[i].Oper); //运算符优先级小于等于栈顶元素
while((!tool.empty())&&priority(tool.top())>=y){
r.Oper =tool.top();
r.sign =2;
suffix.push_back(r); //保存到后缀表达式并弹出
tool.pop();
}
tool.push(nifix[i].Oper); //将这个运算符入栈
}
}
}
while(!tool.empty()){
r.Oper =tool.top(); //以上步骤进行完,栈里还有运算符,全部弹出,存到后缀表达式
r.sign =2;
suffix.push_back(r);
tool.pop();
}
}
double result(){ //后缀表达式计算
int o=suffix.size();
while(suffix.size()!=1){
int i=0;
for(;i<=o-3;){
if((i+2<suffix.size())&&suffix[i].sign==1
&&suffix[i+1].sign==1&&suffix[i+2].sign==2){
suffix[i].num=calcu(suffix[i].num,suffix[i+1].num,suffix[i+2].Oper);
suffix.erase(suffix.begin()+i+1); //这一个步骤执行之后,原来的i+2,变成了i+1;
suffix.erase(suffix.begin()+i+1); //所以这里再写i+2就是错的了
o-=2; //总长度减2
}
else i++;
}
}
return suffix[0].num;
}
bool pre(string a){ //为了防止有些人只输入一个确定的数字
int n=a.length();
bool f=false;
if(n==1){ //一个1位的数字
if(a[0]>='0'&&a[0]<='9')
return true;
return false;
}
else{
if(a[0]=='+'||a[0]=='-')
//第一位是'+','-',(这里不再处理带括号的单个实数,认为它是合法的)
{
if(a[1]=='.') return false;
else{
for(int i=2;i<n;i++){
if(a[i]!='.'&&(a[i]<'0'||a[i]>'9'))
return false;
}
return true;
}
}
else if(a[0]>='0'&&a[0]<='9'){ //第一位是数字
for(int i=1;i<n;i++){ //判断之后有没有除了数字和'.'的元素
if(a[i]!='.'&&(a[i]<'0'||a[i]>'9'))
return false;
}
return true;
}
}
}
void screen(){
system("cls");
cout<<"\t\t\t\t☆☆☆-----------------------------------------☆☆☆"<<endl;
cout<<"\t\t\t\t| |"<<endl;
cout<<"\t\t\t\t| 题目6:模拟计算器 |"<<endl;
cout<<"\t\t\t\t| |"<<endl;
cout<<"\t\t\t\t| Nifix Expression Calculator For Windows |"<<endl;
cout<<"\t\t\t\t| |"<<endl;
cout<<"\t\t\t\t| 支持 '+' '-' '*' '/' '%' '#(幂)'运算 |"<<endl;
cout<<"\t\t\t\t| |"<<endl;
cout<<"\t\t\t\t| ID:311709000524 |"<<endl;
cout<<"\t\t\t\t| |"<<endl;
cout<<"\t\t\t\t| By---宋子洋 |"<<endl;
cout<<"\t\t\t\t☆☆☆-----------------------------------------☆☆☆"<<endl;
cout<<endl<<endl<<"请输入一个表达式(输入'@'退出)"<<endl<<endl;
}
int main(){
system("color 0A");
screen();
while(cin>>a){
if(a=="@") {
cout<<endl<<"成功退出!!!"<<endl;
break;
}
else if(pre(a)){
if(a.length()==1||a[0]=='-'||a[0]>='0'&&a[0]<='9')
cout<<endl<<"计算结果为:"<<a<<endl;
else{
cout<<endl<<"计算结果为:";
for(int i=1;i<a.length();i++){
cout<<a[i];
}}
cout<<endl;
cout<<endl<<"请按Enter键继续!!!"<<endl;
a.clear(); //全局变量初始化
getchar();
getchar();
screen();
}
else if(!judge(a)){
cout<<endl<<"表达式非法,请重新输入!!!"<<endl;
a.clear();
getchar();
getchar();
screen();
continue;
}
else {
string after;
after=dealneg(a);
strtonif(after);
niftosuf();
cout<<endl<<"计算结果为:"<<result()<<endl;
cout<<endl<<"请按Enter键继续!!!"<<endl;
a.clear(); //全局变量初始化
vector<mix>().swap(suffix);
q=0;
getchar();
getchar();
screen();
}
}
return 0;
}