计算(calc)

【题目描述】小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”，求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法)

【输入】共1行，为一个算式。

【输出】共1行，就是密码。

【输入样例】 1+(3+2)(7^2+69)/(2)

【输出样例】 258

stack<char>op;

stack<int>sts;

map<char,int>opp;

这题我们可以用两个stack和一个map来做这道题，其中一个stack用来存储数字，还有一个stack用来存储符号，map映射char和int将各个符号的优先级映射为int类型首先给各个符号附上优先级，先不用管括号，遇到反括号就可以直接弹出，括号内的所有符号进行计算

opp<'+'>=opp<'-'>=1;

opp<'*'>=opp<'/'>=2;

opp<'^'>=3;

#include <iostream>

#include <cmath>

#include <stack>

#include <string>

using namespace std;

stack<int> s1;//存放数的栈

stack<char> s2;//存放符号

string s;//用string类型存储更方便，比如字符串拼接

int level(char p)//符号优先级

{

	if (p == '+' || p == '-')	return 1;

	if (p == '*' || p == '/')	return 2;

	if (p == '^')	return 3;

	return 0;

}

void calc()

{

	int n, m;

	n = s1.top();//栈是个倒序的，所以第二个操作数在栈顶

	s1.pop();

	m = s1.top();//第一个操作数

	s1.pop();

	char z = s2.top();//符号

	s2.pop();

	switch (z)

	{

		case '+':s1.push(m + n);break;

		case '-':s1.push(m - n);break;

		case '*':s1.push(m * n);break;

		case '/':s1.push(m / n);break;

		case '^':s1.push(pow(m, n));break;

		default:

			break;

	}

	return;

}

int main()

{

	cin >> s;

	s = '(' + s + ')';//把s两端添加括号，方便最后运算

	int i = 0;//下标

	char ch = '(';//首位的(

	do

	{

		if (ch == '(')//如果符号是左括号，直接入栈即可

		{

			s2.push('(');

		}

		else if (ch == ')')

		{

			while (s2.top() != '(') calc();//计算括号里所有的

			s2.pop();//弹出(

		}

		else if (ch >= '0' && ch <= '9' || ch == '-' && s[i - 1] == '(')//如果这是个数，或者是个负数

		{

			int x, y;//x代表数，y代表符号

			if (ch == '-') x = 0, y = -1;

			else x = ch - '0', y = 1;

			char ch0 = s[++i];//ch的下一个符号是否是数字呢？ 会不会出现不是多位数呢？

			while ('0' <= ch0 && ch0 <= '9')//如果是数字，那么我们就把他转换成int型的整数啊

			{

				x = x * 10 + (ch0 - '0');//简单的数学知识

				ch0 = s[++i];//等同于i = i + 1; ch0 = s[i];

			}

			x *= y;//正负

			s1.push(x);//就找到一个数字了，把他入栈

			i--;

		}

		else//是个符号

		{

			while (level(ch) <= level(s2.top()))//当前运算符不超过栈顶运算，先算栈顶运算

			//举个例子, 1+2*3 乘法比加法优先级高，那么先算乘法

			{

				calc();

			}

			s2.push(ch);//直到当前运算符高于栈顶运算符再把运算符存栈

		}

	} while (ch = s[++i]);//这里挺巧的，读到空字符也就终止了

	cout << s1.top() << endl;//栈顶就是答案咯

	return 0;

}

巴特西

计算(calc)

计算(calc)

最新文章

热门文章