后缀表达式求值算法

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <string>
using namespace std;
struct node {
	double num;
	char op;
	bool flag;//"true" is number,"false" is operator;
};
string str;
stack <node> s;
queue <node> q;
map<char, int> oper;
void Change()
{
	double num;
	node temp;
	for (int i = 0; i < str.length(); i++)
	{
		if (str[i] >= '0' && str[i] <= '9')
		{
			temp.flag = true;
 			temp.num = str[i] - '0';
			q.push(temp);
		}
		else if (str[i] == '(')//注意if和else if是平行配对的，不能一直if最后用else，不然自动与上一个if配对
		{
			temp.flag = false;
			temp.op = '(';
			s.push(temp);
		}
		else if (str[i] == ')')
		{
			while (s.top().op != '(')
			{
				q.push(s.top());
				s.pop();
			}
			s.pop();
		}
		else
		{
			temp.flag = false;
            //下面用while不用if，非常重要
			while (!s.empty() && oper[str[i]] <= oper[s.top().op])//注意：凡是运用了top()函数、front()函数、back()函数等函数，都需要判断非空与否
			{
				q.push(s.top());
				s.pop();
			}
			temp.op = str[i];
			s.push(temp);
		}
	}
	while (!s.empty())//把栈里的符号弹出至队列中
	{
		q.push(s.top());
		        s.pop();
	}
}
double Calculate()
{
	double n1, n2;
	node cur, temp;
	while(!q.empty())
	{
		cur = q.front();//遍历队首元素
		q.pop();
		if (cur.flag == true)
		{
			s.push(cur);
		}
		else
		{
			n1 = s.top().num;
			s.pop();
			n2 = s.top().num;
			s.pop();
			temp.flag = true;
			 if (cur.op == '+')
				temp.num = n2 + n1;
			 else if (cur.op == '-')
				temp.num = n2 - n1;
			 else if (cur.op == '*')
				temp.num = n2 * n1;
			 else 
				temp.num = n2 / n1;
			s.push(temp);
		}
	}
		return s.top().num;
}
int main()
{
	//oper['('] = 0;//不参与运算，不要管它
	oper['+'] = oper['-'] = 1;
	oper['*'] = oper['/'] = 2;
	//need a extra way to erase the space
	cin >> str;
	while (!s.empty()) 
		s.pop();
	Change();
	cout << Calculate() << endl;
}