表达式计算

时间 2013-04-30

原文原文链接

题目

输入一个表达式，计算出它的值。运算符有 + - × / （）。

思路

这是我们学栈时碰到的一个问题，大体方法是利用双栈把中缀表达式转换成后缀表达式进行计算

------------------------------------------------------------------------------------------------

1.拆分数字与运算符

：遇到运算符截断、存储、清空。

2.转后缀表达式

：栈A存放后缀表达式，栈B存放运算符

记 B栈顶运算符为a1,当前运算符为a2（若a2为数字直接 a2->A ）

1）若 a1>a2，a1->A，a2->B

1）若 a1<a2，a2->B；

2）若 a1>=a2

1.若a1>a2，a1->A；（只要该条件满足则一直执行，使得优先级高的运算符放在A中）

2.将高级运算符都赶走后，要判断a1=a2 ?（即是否为()相遇）

如果为左右括号的话就把做括号弹出，否则把a2->B。（注意与1的区别，一个）可以一直赶走比它高级的运算法，但是只能抵消一个左括号）

PS: a1>a2 表示在此式中先算a1再算a2，a1与a2的关系在初始化中建立。

3.计算后缀表达式

: 从左往右扫描，遇到运算符则处理前两位数字

-------------------------------------------------------------------------------------------------

代码

#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <cstdio>
#include <cstdlib>
using namespace std;
string ss;
vector<double> ans;
vector<string> s,A;
stack<char> B;
int cmp[8][8]={	{1,1,-1,-1,-1,1},
				{1,1,-1,-1,-1,1},
				{1,1,1,1,-1,1},
				{1,1,1,1,-1,1},
				{-1,-1,-1,-1,-1,0},
				{1,1,1,1,0,0}};
int gec[333];
bool isNum(char a){
	switch(a){
			case '+':
			case '-':
			case '*':
			case '/':
			case '(':
			case ')':
				return false;
	}
	return true;
}
void init(){
	gec['+']=0;
	gec['-']=1;
	gec['*']=2;
	gec['/']=3;
	gec['(']=4;
	gec[')']=5;
}
void Quit(int v){
	cout << "ERROR : ";
	switch(v){
		case 1:
			cout << "DIVISION BY 0";
			break;
		case 2:
			cout << "PARENTHESES ARE NOT EVEN";
			break;
	}
	cout << endl;
	exit(0);
}
double gen(string s){
	double tmp;
	sscanf(s.c_str(),"%lf",&tmp);
	return tmp;
}
void check(){
	stack<char> q;
	for (string::size_type i(0);i!=ss.size();i++){
		if (ss[i]=='(') q.push(ss[i]);
		if (ss[i]==')') {
			if (q.empty()) Quit(2);
			if (q.top()=='(') q.push(ss[i]);
			else q.pop();
		}
	}
	if (q.size()) Quit(2);
}
void ready(){
	cin >> ss;
	check();
	ss+=')';
	string str="";
	for (string::size_type i(0);i!=ss.size();i++){
		if (isNum(ss[i])){
			str+=ss[i];
		}else {
			if (str.size()) s.push_back(str);
			str=ss[i];
			s.push_back(str);
			str="";
		}
	}
}
void changetype(){
	B.push('(');
	for (unsigned int i(0);i!=s.size();i++){
		if (isNum(s[i][0])){
			A.push_back(s[i]);
		}else{
			char ch=s[i][0];
			if (cmp[gec[B.top()]][gec[ch]]<0){
				B.push(ch);
			}else 
			if (cmp[gec[B.top()]][gec[ch]]>=0){
				string str;
				while (cmp[gec[B.top()]][gec[ch]]>0){
                    str=B.top();
                    A.push_back(str);
                    B.pop();
                }
                if (cmp[gec[B.top()]][gec[ch]]==0){
					B.pop();
				}else{
					B.push(ch);
				}
			}
			
		}
	}
}
void calcit(){
	for (int i(0);i!=A.size();i++){
		if (isNum(A[i][0])) {
			ans.push_back(gen(A[i]));
		}else{
			double a1=ans[ans.size()-2];
			double a2=ans[ans.size()-1];
			printf("%.2f%c%.2f=",a1,A[i][0],a2);
			switch (A[i][0]){
				case '+':
					a1+=a2;
					break;
				case '-':
					a1-=a2;
					break;
				case '*':
					a1*=a2;
					break;
				case '/':
					if (!a2){
						Quit(1);
					}
					a1/=a2;
					break;
			}
			printf("%.2f\n",a1);
			ans.pop_back();
			ans[ans.size()-1]=a1;
		}
	}
	printf("%.3f\n",ans[0]);
}
int main(){
	init();
	ready();
	changetype();
	calcit();
	return 0;
}