通过逆波兰式,做带括号的混合运算

大耗子 2020年03月01日 151次浏览

文章链接:https://codemouse.online/archives/2020-03-01-101711

逆波兰式(

Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后)。
如(a+b)*c-(a+b)/e的后缀表达式为:
(a+b)*c-(a+b)/e
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-

算法实现:

  1. 判断是否为数字,是数字则放入队列中,回到第一步,不是则下一步。
  2. 是左括号直接放入符号栈中,回到第一步,不是则下一步。
  3. 是右括号,则弹出符号栈顶元素,放入队列,重复弹出,直到弹出左括号,左括号不加入队列,回到第一步,不是则下一步。
  4. 是操作符(+-*/),如符号栈顶为空或栈顶为左括号或栈顶操作符优先级没有目前操作符优先级高,则直接将操作符放入符号栈,否则将栈顶元素出栈,添加到队列,直到不满足条件,回到第一步。

代码实现

#include <stack>
#include <string>
#include <iostream>
#include <queue>
using namespace std;

stack<char> opStack;
stack<double> numStack;
// 判断是否为操作符
int isOp(char a)
{
	if (a == '+' || a == '-' || a == '*' || a == '/')
		return true;
	return false;
}
// 判断操作符的优先级
int isMax(char a, char b)
{
	int ay = 0, by = 0;
	if (a == '*' || a == '/')
		ay = 1;
	if (b == '*' || b == '/')
		by = 1;
	if (ay > by)
		return true;
	return false;

}
// 乘除法运算
void calcula(char op)
{
	double a, b;
	b = numStack.top();
	numStack.pop();
	a = numStack.top();
	numStack.pop();
	switch (op)
	{
	case '*':
		numStack.push(a*b);
		break;
	case '/':
		numStack.push(a / b);
		break;
	case '-':
		numStack.push(a - b);
		break;
	case '+':
		numStack.push(a + b);
		break;
	}
}
// 获取逆波兰式
queue<string> getInversePoland(char *str)
{
	queue<string> setQue;
	char buf[1024] = { 0 };
	char *shu = buf;
	char *c = str;
	int dian = 0;
	while (*c != '#')
	{
		while (isdigit(*c) || *c == '.')
		{//获取到数字
			if (dian > 1)
			{
				printf("小数点输入过多\n");
				exit(-1);
			}
			if (buf[0] == '.')
			{
				printf(".不能放在数字首位\n");
				exit(-1);
			}
			if (*c == '.')
				dian++;
			*shu++ = *c++;
			if (!(isdigit(*c) || *c == '.')){

				setQue.push(buf);
				memset(buf, 0, 1024);
				shu = buf;
				c--;
				break;
			}
		}
		if (*c == '(')
		{
			opStack.push('(');
		}
		if (*c == ')')
		{
			while (!opStack.empty() && opStack.top() != '(')
			{
				setQue.push(&opStack.top());
				opStack.pop();

			}
			if (opStack.empty())
			{
				printf("缺少左括号\n");
				exit(-1);
			}

			opStack.pop();//释放掉'('
		}
		while (isOp(*c))//操作符的操作
		{
			if (opStack.empty() || opStack.top() == '(' || isMax(*c, opStack.top()))
			{
				opStack.push(*c);
				break;
			}
			else
			{
				setQue.push(&opStack.top());
				opStack.pop();
			}
		}
		c++;
		dian = 0;
	}
	// 对剩余的操作符操作
	while (!opStack.empty())
	{
		setQue.push(&opStack.top());
		opStack.pop();
	}
	return setQue;
}
// 解析逆波兰式
void analysisInversePoland(queue<string> setQue)
{
	while (!setQue.empty()){
		string tmp = setQue.front();
		if (isdigit(tmp[0]))
			numStack.push(atof(tmp.c_str()));
		else
			calcula(tmp[0]);
		setQue.pop();
	}
	if (numStack.size() == 1)
		printf(" = %f ", numStack.top());
	else
		printf("运算出错,输入数据或符号有误\n");

}
void main()
{

	char str[1024] = { "1.2+2.2*3.3-(4.5+5.1)/6.5#" };
	//scanf("%s",str);
	// 获取逆波兰式
	queue<string> setQue = getInversePoland(str);
	// 对获取的逆波兰式运算
	analysisInversePoland(setQue);
	
}