first_com.cpp

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

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

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

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

// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
    
// <学生姓名>:毛宁宇
#include<iostream>
#include<stack>
using namespace std;
char num[100]={0};//存放表达式中的数字
int a,b;//用于在栈中提取两个变量
stack<int> s1;//s1用于存放数字
stack<char> s2;//存放符号
int calculate(){//把表达式中的char算成int型的数
	int i,j,sum=0;
	i=strlen(num);
	int n=1;
	for(j=i-1;j>=0;j--){
		sum+=(num[j]-'0')*n;
		n*=10;
	}
	return sum;
}
void add(){//加
	a=s1.top();
	s1.pop ();
	b=s1.top ();
	s1.pop ();
	s1.push (a+b);
	s2.pop ();
}
void minus(){//减
	a=s1.top();
	s1.pop ();
	b=s1.top ();
	s1.pop ();
	s1.push (b-a);
	s2.pop ();
}
void multiply(){//乘
	a=s1.top();
	s1.pop ();
	b=s1.top ();
	s1.pop ();
	s1.push (a*b);
	s2.pop ();
}
int divide(){//除
	int sigh=0;
	a=s1.top();
	if(a==0){
		cout<<"对不起，除数不能为0"<<endl;
		sigh=1;
	}
	else{
	s1.pop ();
	b=s1.top ();
	s1.pop ();
	s1.push (b/a);
	s2.pop ();
	}
	return sigh;
}
int main(){
	cout<<"                       ************************"<<endl;
	cout<<"                       欢迎使用00748032计算系统"<<endl;
	cout<<"                       ************************"<<endl;
	cout<<"请输入您要计算的表达式：";
	char input;
	int i=0,flag=0;
	while(cin.get(input)){
		if(input!='\n'){//首先，如果输进来的不是回车
			if(input>='0'&&input<='9'){//若是数字
				flag=1;
				num[i++]=input;//把数字放到num中
			}
			if((input>='9'||input<='0')){//若不是数字
				if((input=='+'||input=='-'||input=='*'||input=='/'||input=='('||input==')')){//若输入均为有效字符
					if(flag){
						s1.push(calculate());//把数字串计算成数压入栈中
						i=0;
						flag=0;
						memset(num,0,sizeof(num));
					}
				}
				else{//若输入为非法字符，则退出程序
					cout<<"对不起，您的输入中含有非法字符。"<<endl;
					return 0;
				}
			}
		}
		if(input=='\n'){//若输进来的是回车
			if(flag==1){//如果num中还有数字，则放到栈中
				s1.push(calculate());
				i=0;
				flag=0;
				memset(num,0,sizeof(num));
			}
			break;
		}
		//下面仔细考察输进来的是什么字符
		if(input==')'){//当输入为闭括号时
			int flag2=0;
			if(s2.empty()){//先判断栈是否为空，若为空，则表示括号不匹配
				cout<<"括号不匹配，表达式错误"<<endl;
				return 0;
			}
			else{//非空，则一个一个弹出运算，遇到第一个开括号为止
				while(!s2.empty ()&&flag2==0){
					switch(s2.top ()){
					case '+':add();break;
					case '-':minus();break;
					case '*':multiply();break;
					case'/':if(divide())return 0;//当除数不为零时才对
							break;
					case'(':s2.pop ();
							flag2=1;//做标记遇到了
							break;
					default:break;
					}
				}
			}
			if(flag2==0){//若栈都空了还没看到开括号，则括号不匹配
				cout<<"括号不匹配，表达式错误"<<endl;
				return 0;
			}
		}
		if(input=='(')//当输入为开括号时，将其入栈
			s2.push(input);
		if(input=='+'||input=='-'){//当输入为+或-时
			while(!s2.empty ()&&s2.top ()!='('){//栈非空且栈顶不是开括号时
				switch(s2.top()){
				case '+':add();break;
				case '-':minus();break;
				case '*':multiply();break;
				case'/':if(divide())return 0;//当除数不为零时才对
						break;
				default:break;
				}
			}
			s2.push (input);//将输入的运算符压栈
		}
		if(input=='*'||input=='/'){//当输入为*或/时
			if(!s2.empty ()&&s2.top ()!='('&&(s2.top ()=='*'||s2.top ()=='/')){//栈非空且栈顶不是开括号时
                                                                        //且栈顶运算符优先级不低于输入运算符的优先级

				switch(s2.top ()){
				case '*':multiply();break;
				case '/':if(divide())return 0;//当除数不为零时才对
						break;
				default:break;
				}
			}
			s2.push (input);//将输入的运算符压栈
		}	
	}
	if(s1.empty ())return 0;//若开始输入只为回车，则直接退出
	while(s2.empty ()==0){//最后如果栈内还有运算符，则继续运算
		switch(s2.top()){
		case '+':add();break;
		case '-':minus();break;
		case '*':multiply();break;
		case'/':if(divide())return 0;//当除数不为零时才对
				break;
		case '(':cout<<"括号不匹配，表达式错误"<<endl;
				return 0;
		default:break;
		}
	}
	cout<<"您要求的表达式的值为："<<s1.top ()<<endl;
	return 0;
}