简单计算器

题目描述：

读入一个只包含+-*/的非负整数计算表达式，计算该表达式的值。

cal.cpp

#include "cstdio"
#include "stack"
#include "queue"
#include "string"
#include "map"
#include "iostream"

using namespace std;

struct node {
	double num; //操作数
	char op;	//操作符
	bool flag;	//true表示操作数；false表示操作符
};

string str;
stack<node> s;	//操作符栈
queue<node> q;	//后缀表达式序列
map<char, int> op;

void change()	//将中缀表达式转化为后缀表达式
{
	double num;
	node temp;
	for(int i = 0; i < str.length(); )
	{
		if(str[i] >= '0' && str[i] <= '9')	//如果是数字
		{
			temp.flag = true;	//标记为数字
			temp.num = str[i++] - '0';	//记录这个操作数的第一个数位
			while(i < str.length() && str[i] >= '0' && str[i] <= '9')
			{
				temp.num = temp.num * 10 + (str[i] - '0');	//更新这个操作数
				i++;
			}
			q.push(temp); //将这个操作数压入后缀表达式的队列
		}
		else
		{
			temp.flag = false;	//标记是操作符
			//只要操作栈的栈顶元素比该操作符优先级高
			//就把操作符栈顶元素弹出到后缀表达式的队列中
			while(!s.empty() && op[str[i]] <= op[s.top().op])
			{
				q.push(s.top());
				s.pop();
			}
			temp.op = str[i];
			s.push(temp);	//把该操作符压入操作栈中
			i++;
		}
	}
	//如果操作栈中还有操作符，就把它弹到后缀表达式队列中
	while(!s.empty())
	{
		q.push(s.top());
		s.pop();
	}
}

double cal()	//计算后缀表达式
{
	double temp1, temp2;
	node cur, temp;
	while(!q.empty())	//只要后缀表达式队列非空
	{
		cur = q.front();	//cur 记录队首元素
		q.pop();
		if(cur.flag == true) s.push(cur);	//如果是操作数直接压入
		else	//如果是操作符
		{
			temp2 = s.top().num;
			s.pop();
			temp1 = s.top().num;
			s.pop();
			temp.flag = true;	//临时记录操作数
			if(cur.op == '+') temp.num = temp1 + temp2;
			else if(cur.op == '-') temp.num = temp1 - temp2;
			else if(cur.op == '*') temp.num = temp1 * temp2;
			else temp.num = temp1 / temp2;
			s.push(temp);	//把该操作数压入栈底
		}
	}
	return s.top().num; //栈顶元素就是后缀表达式值
}

int main()
{
	op['+'] = op['-'] = 1;
	op['*'] = op['/'] = 2;
	
	while(getline(cin, str), str != "0")
	{
		
		for(string::iterator i = str.begin(); i != str.end(); i++)
		{
			if(*i == ' ') str.erase(i);
		}	
		while(!s.empty()) s.pop();
		change();
		printf("%.2f\n",cal());
	}
	return 0;
}
	
			
			
			

参考文献：

胡凡,曾磊. 算法笔记 [M] 北京：机械工业出版社，2016.