简单计算器
输入一个只包含 + - * / 运算符且运算数都为非负整数的表达式，请计算该表达式的值。
输入格式:
测试数据有多组。对于每组测试，输入一个字符串（长度不超过200）表示的表达式，整数和运算符之间用一个空格分隔。若输入0则输入结束，相应的结果不要输出。测试数据保证没有非法表达式。
输出格式:
对于每组测试，输出表达式的值，结果保留2位小数。
输入样例:
1 + 2
4 + 2 * 5 - 7 / 11
0
输出样例:
3.00
13.36
**出处:
HDOJ 1237**
浙大计算机研究生复试上机考试-2006年
代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
解题代码
#include<bits/stdc++.h>
using namespace std;
#define MAXSIZE 100
template <class T>
struct LinkStack{
public:
void initStack();
void Push(T num);
void Pop();
T Top();
bool isFull();
bool isEmpty();
void Clear();
struct stackNode;
private:
stackNode *top;
int num;
};
template<class T>
struct LinkStack<T>::stackNode{
T data;
stackNode *next;
// stackNode(T num){
// this->data=num;
// }
};
template<class T>
void LinkStack<T>::initStack()
{
top= new stackNode();
top->next=NULL;
this->num=0;
}
template<class T>
void LinkStack<T>::Push(T num){
if(isFull()){
//cout<<"stack is Full!"<<endl;
return;
}
stackNode *p = new stackNode();
p->data = num;
p->next=top->next;
top->next=p;
this->num++;
}
template<class T>
void LinkStack<T>::Pop()
{
if(isEmpty()){
//cout<<"stack is Empty!"<<endl;
return;
}
stackNode *p=top->next;
top->next=p->next;
free(p);
this->num--;
}
template<class T>
bool LinkStack<T>::isEmpty()
{
if(top->next==NULL){
return true;
}
return false;
}
template<class T>
bool LinkStack<T>::isFull()
{
if(this->num==MAXSIZE){
return true;
}
return false;
}
template<class T>
T LinkStack<T>::Top()
{
if(!isEmpty()){
//cout<< top->next->data<<<<endl;
return top->next->data;
}
return NULL;
}
template<class T>
void LinkStack<T>::Clear()
{
if(!isEmpty()){
stackNode *p;
while(top->next!=NULL){
p=top->next;
top->next=p->next;
free(p);
}
}
}
double getAns(double a,double b,char opt){
switch(opt)
{
case '+':
return a+b;
case '-':
return a-b;
case '*':
return a*b;
case '/':
return a/b;
}
}
int main()
{
string str;
LinkStack<double> *NumStack = new LinkStack<double>();
NumStack->initStack();
LinkStack<char> *OptStack = new LinkStack<char>();
OptStack->initStack();
while(getline(cin,str)&&str!="0"){
NumStack->Clear();
OptStack->Clear();
str=str+" ";
float s =0;
int len = str.size();
for(int i=0;i<len;i++){
if(str[i]>='0'&&str[i]<='9'){
s=s*10+(str[i]-'0');
}
if(str[i-1]>='0'&&str[i-1]<='9'&&str[i]==' '){
NumStack->Push(s);
s=0;
}
if((str[i]<'0'||str[i]>'9')&&str[i]!=' '){
if(str[i]=='+'||str[i]=='-'){
if(!OptStack->isEmpty()){
while(!OptStack->isEmpty()){
double b = NumStack->Top();
NumStack->Pop();
double a = NumStack->Top();
NumStack->Pop();
//cout<<a<<OptStack->Top()<<b<<endl;
NumStack->Push(getAns(a,b,OptStack->Top()));
OptStack->Pop();
}
}
OptStack->Push(str[i]);
}else if(str[i]=='*'||str[i]=='/'){
if(!OptStack->isEmpty()){
while(OptStack->Top()=='*'||OptStack->Top()=='/'){
double b = NumStack->Top();
NumStack->Pop();
double a = NumStack->Top();
NumStack->Pop();
//cout<<a<<OptStack->Top()<<b<<endl;
NumStack->Push(getAns(a,b,OptStack->Top()));
OptStack->Pop();
}
}
OptStack->Push(str[i]);
}
}
}
while(!OptStack->isEmpty()&&!NumStack->isEmpty()){
double b = NumStack->Top();
NumStack->Pop();
double a = NumStack->Top();
NumStack->Pop();
NumStack->Push(getAns(a,b,OptStack->Top()));
OptStack->Pop();
}
printf("%.2lf\n",NumStack->Top());
}
}
解题思路
我写了一个用template< class T>写了一个模板类，就是相当于写模板的方式，在定义这个类栈的时候，我们可以直接声明这个类栈中的T是什么类型的，比如double，char，像我的代码就写了一个栈类，但是我用的时候装了两个类型的栈，一个是double类型的一个是char类型的，然后用的是链栈
题目里只有 + - * /，所以其他的不用考虑，我们使用getline输入一行字符串，然后逐个取出，这时候，然后取到运算符的时候，判断运算符的优先级，如果栈顶的运算符和当前读取的运算符相比之下，优先级要高或者是同级，那么我们就要先将存储数字的栈中的值一个个取出来运算后，再将我们当前的运算符存入栈中，最后将剩余的取出运算就可以了。
