递归版.cpp

表达式求值的栈算法和递归算法

// 我真诚地保证：
    
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。

// 在此，我感谢 XXX, …, XXX对我的启发和帮助。下面的报告中，我还会具体地提到
// 他们在各个方法对我的帮助。
 
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。

// 我从未抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。

// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
    
// <学生姓名>:毛宁宇
#include<iostream>
using namespace std;
int wrong=0;
char formula[100];
int calculate(int first,int last){//把一个表达式拆分成一个符号和两个表达式的值，由此递归
	int i,j,k,flag1=0,flag2=0;
	for(i=first;i<=last;i++){
		switch(formula[i]){
			case '+':
			case '-':flag1=1;j=i;break;//如果是+或-做记号
			case '*':
			case '/':flag2=1;k=i;break;//如果是*或/做记号
			case '(':while(formula[i]!=')'&&i<=last)i++;//空格不管跳过当成一个值
					 if(i==last+1){cout<<"括号不匹配"<<endl;wrong=1;return 0;}//没闭括号与开括号匹配
					 break;
			case '0'://当是数字时都跳过
			case '1':
			case '2':
			case '3':
			case '4':
			case '5':
			case '6':
			case '7':
			case '8':
			case '9':break;
			default:cout<<"输入中含有非法字符或括号不匹配"<<endl;wrong=1;return 0;//看是否有非法输入符
		}
	}
	if(flag1){//有加减则先算加减
		if (formula[j]=='+')return calculate(first,j-1)+calculate(j+1,last);
		if (formula[j]=='-')return calculate(first,j-1)-calculate(j+1,last);
	}
	else{//没加减
		if(flag2){//有乘除则算乘除
			if (formula[k]=='*')return calculate(first,k-1)*calculate(k+1,last);
			if (formula[k]=='/'){
				if(calculate(k+1,last)==0){
					cout<<"除数不能为0"<<endl;
					wrong=1;
					return 0;
				}
				return calculate(first,k-1)/calculate(k+1,last);}
		}
		else{//没乘除则可能只是个数或是个括号括起来的子表达式
			if(formula[first]=='('&&formula[last]==')')return calculate(first+1,last-1);//若是子表达式
			else {//若是个值，则返回这个值
				char tmp[100];
				int o,p=0;
				for(o=first;o<=last;o++)
					tmp[p++]=formula[o];
				return atoi(tmp);
			}
		}
	}
	return 0;
}
int main(){
	cout<<"                *******************************************"<<endl;
	cout<<"                欢迎使用00748032计算系统*最终修订递归算法版"<<endl;
	cout<<"                *******************************************"<<endl;
	while(1){//循环输入系统
		cout<<"请选择您要进行的操作，1代表求表达式的值，0代表退出，按回车确定：";
		int x,y;
		cin>>y;
		switch(y){
			case 1:
				cout<<"请输入您要计算的表达式（如：23+(34*45)/(5+6+7)空格将被视为非法字符）："<<endl;
				wrong=0;
				cin>>formula;
				x=calculate(0,strlen(formula)-1);
				if(wrong==0)cout<<"您所求表达式的值为："<<x<<endl;break;
			case 0:return 0;
			default:break;
		}
	}
}