中缀转后缀和计算

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

//判断是否是运算符
bool is_operator(char ch)
{
	if (ch == '+' || ch == '-' || ch == '*' || ch == '/' )
	{
		return true;
	}
	return false;
}

//获取优先级
int priority(char ch)
{
	switch (ch)
	{
	case '+':
		return 1;
	case '-':
		return 1;
	case '*':
		return 2;
	case '/':
		return 2;
	default:
		return 0;
	}
}

//中缀转前缀
string intfix_to_posfix(const string& infix)
{
	string posfix;
	stack<char> s;

	for (char ch : infix)
	{
		//遇到数字就直接输出到后缀表达式中
		if (isdigit(ch))
		{
			posfix += ch;
		}
		//遇到操作符
		else if (is_operator(ch))
		{
			//获取操作符优先级
			int cur = priority(ch);
			// 如果栈不空，栈顶为运算符，并且栈顶运算符的优先级大于等于当前运算符的优先级
			while (!s.empty() && is_operator(s.top()) && priority(s.top()) >= cur)
			{
				// 将栈顶运算符弹出并添加到后缀表达式中
				posfix += s.top();
				s.pop();
			}
			//否则就将当前操作符入栈
			s.push(ch);
		}
		// 如果当前位置是右括号
		else if (ch == '(')
		{
			//入栈
			s.push(ch);
		}
		// 如果当前位置是右括号
		else if (ch == ')')
		{
			// 不断将栈中的元素弹出，直到遇到左括号
			while (!s.empty() && s.top() != '(')
			{
				// 将弹出的运算符输出到后缀表达式中
				posfix += s.top();
				s.pop();
			}
			// 如果栈不空且栈顶元素是左括号
			if (!s.empty() && s.top() == '(')
			{
				//丢弃左括号
				s.pop();
			}
		}
	}

	// 如果栈不空，则将栈中所有元素弹出并输出到后缀表达式中
	while (!s.empty())
	{
		posfix += s.top();
		s.pop();
	}

	return posfix;
}

// 计算后缀表达式的值
double evaluate(const string& postfix) 
{
	stack<double> s;
	for (int i = 0; i < postfix.size(); i++) 
	{
		if (isdigit(postfix[i]))
		{
			s.push(postfix[i] - '0');
		}
		else
		{
			double op2 = s.top();
			s.pop();
			double op1 = s.top();
			s.pop();
			switch (postfix[i]) 
			{
			case '+':
				s.push(op1 + op2);
				break;
			case '-':
				s.push(op1 - op2);
				break;
			case '*':
				s.push(op1 * op2);
				break;
			case '/':
				s.push(op1 / op2);
				break;
			}
		}
	}
	return s.top();
}



int main()
{

	string infix = "9+(3-1)*3+3/2";
	string posfix = intfix_to_posfix(infix);

	cout << "infix = " << infix << endl;
	cout << "posfix = " << posfix << endl;
	cout << "result = " << evaluate(posfix) << endl;


	return 0;
}