嵌入式

编程与应用
posts - 14, comments - 1, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

链式栈及用其测试的计算器

Posted on 2010-04-17 10:59 陈显锋 阅读(297) 评论(0)  编辑 收藏 引用 所属分类: 数据结构程序
#ifndef STACK_CLASS
#define STACK_CLASS
#include<iostream>
using namespace std;

template <class T>
class Stack
{
public:
    virtual bool Push(T x)=0;
    virtual bool Pop()=0;
    virtual T Top() const=0;
    virtual void Clear()=0;
    virtual bool IsEmpty() const=0;
};

#endif//STACK_CLASS
#ifndef LINKEDSTACK_CLASS
#define LINKEDSTACK_CLASS
//#include"Stack.h"
template <class T> class LinkedStack;
template <class T>

class Node
{
    private:
        T elements;
        Node<T> *link;
        friend class LinkedStack<T>;
};

template <class T>
class LinkedStack//:public Stack<T>
{ 
  public:
    LinkedStack(){top=NULL;}
    ~LinkedStack();
    bool IsEmpty() const { return top==NULL; }
    T Top() const;
    bool Push(T x);
    bool Pop();
    void Clear();
  private:                                  
    Node<T> *top; 
};

#endif//LINKEDSTACK_CLASS

template <class T>
LinkedStack<T>::~LinkedStack()
{
    Node<T>* p=top;
    while(p)
    {
        p=top->link;
        delete top;
        top=p;
    }
}

template <class T>
T LinkedStack<T>::Top() const
{ 
    return top->elements;
}

template <class T>
bool LinkedStack<T>::Push(T x)
{ 
   Node<T>* p=new Node<T>;
   p->elements=x;
   p->link=top;
   top=p;//cout<<top->elements<<" ";
   return true;
}

template <class T>
bool LinkedStack<T>::Pop()
{ 
    if(IsEmpty()){                                  //空栈处理
        cout<<"Underflow"<<endl;   return false;
    }
    Node<T>* p;
   p=top->link;delete top;top=p; return true;
}

template <class T>
void LinkedStack<T>::Clear()
{
    Node<T>* p=top;
    while(p)
    {
        p=top->link;
        delete top;
        top=p;
    }
}
#include<iostream>
#include"LinkedStack.h"
using namespace std;
#include<ctype.h>
#include<math.h>
LinkedStack<float> s;
LinkedStack<char> cs;

int isp(char optr) 
{ 
    switch (optr) 
    { 
    case '=': return 0; 
    case '(': return 1; 
    case '^': return 7; 
    case '*': return 5; 
    case '/': return 5; 
    case '%': return 5; 
    case '+': return 3; 
    case '-': return 3; 
    case ')': return 8; 
    default: return 0; 
    } 
} 

int icp(char optr) 
{ 
    switch (optr)
    {
    case '=': return 0; 
    case '(': return 8; 
    case '^': return 6; 
    case '*': return 4; 
    case '/': return 4; 
    case '%': return 4; 
    case '+': return 2; 
    case '-': return 2; 
    case ')': return 1; 
    default: return 0; 
    } 
} 


void DoOperator(char oper)
{
    float oper1,oper2;
    oper1=s.Top();
    s.Pop();
    oper2=s.Top();
    s.Pop();
    switch(oper)
    {
        case '+':s.Push(oper2+oper1);break;
        case '-':s.Push(oper2-oper1);break;
        case '*':s.Push(oper2*oper1);break;
        case '/':s.Push(oper2/oper1);break;
        case '^':s.Push(pow(oper2,oper1));break;
    }
}

void Run()
{
    char c;float newop;char y;
    cs.Push('=');
    while(cin>>c,c!='='){ 
        //if(c!='+'&&c!='-'&&c!='*'&&c!='/')
        if(isdigit(c)||isalpha(c))
        {
            cin.putback(c);cin>>newop;
            s.Push(newop);
        }
        else if(c==')')
            for(y=cs.Top(),cs.Pop();y!='(';y=cs.Top(),cs.Pop())
                DoOperator(y);
        else
        {
            for(y=cs.Top(),cs.Pop();icp(c)<=isp(y);y=cs.Top(),cs.Pop())
                DoOperator(y);
            cs.Push(y);cs.Push(c);
        }
    }
    while(!cs.IsEmpty()){
        y=cs.Top();
        cs.Pop();
        if(y!='=')
            DoOperator(y);
    }
    cout<<s.Top();
}

int main()
{
    Run();
}



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理