信息学奥赛一本通1356：计算(calc)

【题目网站】

信息学奥赛一本通（C++版）在线评测系统

【题目考点】

栈的使用
后缀表达式的应用
中缀表达式转后缀表达式

【题目思路】

1.输入数据

2.如果遇到数字将放入后缀表达式；

如果遇到符号，分三种情况：

1 遇到符号：用现在的符号和符号准备区的第一个作等级比较（+-等级为1，*/等级为2，^等级为3，括号等级为0）（符号准备区中无符号将直接放进符号准备区）。如果符号准备区的第一个符号等级较高：将符号准备区的第一个符号放进后缀表达式并继续比较。如果现在的符号等级较高：将现在的符号放入符号准备区并重复第二步。

2 遇到左括号：直接放入符号准备区。

3 遇到右括号：右括号不进入符号准备区，将遍历至左括号：如果当前的是左括号，便把左括号删掉。如果当前是符号，将符号放入后缀表达式。

4.现在用后缀表达式算出结果。两个数字和一个符号处理，算出结果，直至结束。

【题目答案】

#include 
#include 
#include 
#include 
#include 
using namespace std;

string data;//中缀表达式
stack s;//符号准备区
stack n;
pair f[1000];//后缀表达式
long long num, fn = 0;

long long cmp(char c){//区分符号
	if (c == '+'){
		return 1;
	}else if (c == '-'){
		return 2;
	}else if (c == '*'){
		return 3;
	}else if (c == '/'){
		return 4;
	}else if (c == '^'){
		return 5;
	}
}

long long lev(char c){//符号等级
	if (c == '+' || c == '-'){
		return 1;
	}else if (c == '*' || c == '/'){
		return 2;
	}else if (c == '^'){
		return 3;
	}else if (c == '('){
		return 0;
	}
}

bool cmp2(char n, char m){//比较函数
	return lev(n) >= lev(m);
}

long long cnt(long long fi, long long se, long long sym){//运算函数
	if (sym == 1) return fi + se;
	if (sym == 2) return fi - se;
	if (sym == 3) return fi * se;
	if (sym == 4) return fi / se;
	if (sym == 5) return pow(fi, se);
}

void pexp(){//后缀表达式算出结果
	for (long long i = 0; i < fn; i++){
		if (!f[i].second){
			long long fi, se;//first和second
			fi = n.top();
			n.pop();
			se = cnt(n.top(), fi, f[i].first);
			n.pop();
			n.push(se);
		}else n.push(f[i].first);
	}
}

int main(){
	cin >> data;
	data.insert(0, "(");
	data += ")";
	for (long long i = 0; i < data.size(); i++){
		if (data[i] <= '9' && data[i] >= '0'){//判断是否为数字
			num = 0;
			while (data[i] <= '9' && data[i] >= '0'){//解决多位数
				num = num * 10 + (data[i] - '0');
				i++;
			}
			i--;
			f[fn] = make_pair(num, true);
			fn++;
		}else{
			if (data[i] == '('){//判断是否为左括号
				s.push('(');
			}else if (data[i] == ')'){//判断是否为右括号
				while (s.top() != '('){
					f[fn++] = make_pair(cmp(s.top()), false);
					s.pop();
				}
				s.pop();
			}else{//为符号
				while (!s.empty() && cmp2(s.top(), data[i])){
					f[fn++] = make_pair(cmp(s.top()), false);
					s.pop();
				}
				s.push(data[i]);
			}
		}
	}
	pexp();
	cout << n.top() << endl;
	return 0;
}

【常见错误】

第10行没有设数字栈
第11行数组设成int型
第12行fn没有设置
第36-38行没有写括号的等级
第68-69行没有加左右括号
第73-76行没有对多位数的应对措施
第77行i没有减1
第91行没有删掉
第98行未输出

信息学奥赛一本通1356：计算(calc)

C/C++/C#相关栏目本月热门文章