学步园

不过目前这个功能太少，而且能算的十分有限，

测试输入为

4+4*5+3=

测试输出为
4 4 5 * + 3 +=27

主要就是了解一下怎么把中缀表达式转化成后缀表达式，然后再利用后缀表达式求值，我后续会完善这个程序，做个真正意义上的计算器。。o(∩_∩)o

转化步骤我搜索了一下，大致如下：

将中缀表达式转换为等价的后缀表达式的过程要使用一个栈放“（”，具体可以按照下面的方式进行。 

（1）从左到右依次扫描中缀表达式的每一个字符，如果是数字字符和圆点“.”则直接将它们写入后缀表达式中。 

（2）如果遇到的是开括号“（”，则将它们压入一个操作符栈（不需要与栈顶操作符相比较），它表明一个新的计算层次的开始，在遇到和它匹配的闭括号“）”时，将栈中的元素弹出来并放入后缀表达式中，直到栈顶元素为“(”时，将栈顶元素“（”弹出（不需要加入后缀表达式），表明这一层括号内的操作处理完毕。 

（3）如果遇到的是操作符，则将该操作符和操作符栈顶元素比较： 

    1、当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取 出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直到当前操作符的优先级大于栈顶元素的优先级小于；

     2、当所遇到的操作符的优先级大于栈顶元素的优先级的时则将它压入栈中。 

（4）重复上述步骤直到遇到中缀表达式的结束符标记“#”，弹出栈中的所有元素并放入后缀表达式中，转换结束

#include<iostream>
#include "stack.h"
#include "deque.h"
bool order[48][48];
void initial();
void judge(char);
bool issym(char);
int calculate();

deque<char>expression;
stack<char>symbol;
stack<int>number;

int main()
{
	initial();	
	using namespace std;
	char ch;
	while (cin>>ch && ch!='@')
	{
		if(ch=='=')
		{
			while (!symbol.empty())
			{
				expression.push_back(symbol.top());
				symbol.pop();
			}
			expression.show();
			cout<<"="<<calculate()<<endl;
			while(!symbol.empty())
				symbol.pop();
			while(!expression.empty())
				expression.pop_back();
			continue;
		}
		if(issym(ch))
			judge(ch);
		else 
		{
			expression.push_back(ch);
			number.push(ch-'0');
		}
	}
	return 0;
}
void initial()
{
	order['+']['+']=order['-']['-']=order['*']['*']=order['/']['/']=true;
	order['*']['+']=order['*']['-']=order['*']['/']=true;
	order['/']['+']=order['/']['-']=order['/']['*']=true;
	order['+']['*']=order['+']['/']=false,order['+']['-']=true;
	order['-']['*']=order['-']['/']=false,order['-']['+']=true;
}
void judge(char s)
{
	if(symbol.empty())
		symbol.push(s);
	else
	{
		if(order[s][symbol.top()])
			symbol.push(s);
		else 
		{
			while(!symbol.empty() && order[symbol.top()][s])
			{
				expression.push_back(symbol.top());
				symbol.pop();
			}		
			symbol.push(s);
		}
	}
}
bool issym(char s)
{
	if(s=='+' || s=='-' || s=='*' || s=='/')return true;
	return false;
}
int calculate()
{
	stack<int>num;
	stack<char>exp;

	while(!expression.empty())
	{
		char ch=expression.front();
		expression.pop_front();
		if(issym(ch))
		{
			int a=num.top();
			num.pop();
			int b=num.top();
			num.pop();

			switch(ch)
			{
			case '+':
				num.push(a+b);
				break;
			case '-':
				num.push(a-b);
				break;
			case '*':
				num.push(a*b);
				break;
			case '/':
				num.push(a/b);
				break;
			}
		}
		else
			num.push(ch-'0');	
	}
	return  num.top();
}