博客

数据结构链栈实现简单计算器的操作

未改进，只能计算输出结果是个位数的数值计算

#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<stdlib.h>
#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAXSIZE 100 

using namespace std;
typedef  char ElemType;
typedef  int Status;


typedef struct StackNode{
     ElemType data; 
     struct StackNode *next;
     int stacksize;//栈可用的最大容量 
}StackNode,*LinkStack;

StackNode *p;

LinkStack OPND;
LinkStack OPTR;

//栈的初始化
Status InitStack (LinkStack &S)
{
   S=NULL;
   return OK;
}


//入栈
Status Push(LinkStack &S,ElemType e) 
{
	//在栈顶插入元素e
	p=new StackNode;//生成新的节点 
	p->data=e;//将新数据域置为e 
	p->next=S;//将新的元素插入栈顶 
	S=p;//修改栈顶指针为p 
	return OK; 
}



//出栈
ElemType Pop(LinkStack &S) 
{
	char e;
    //删除S栈顶元素，用e返回其值
	if(S==NULL)  return ERROR;//栈空
	e=S->data;//将栈顶元素赋值给e
    p=S;//用p临时保存栈顶空间，以被释放 
	S=S->next;//修改栈顶指针	
	delete p;//释放原栈顶元素的空间 	
	return e;
}


//取栈顶元素
ElemType GetTop(LinkStack S) 
{
    //返回S的栈顶元素，不修改栈顶指针
	if(S!=NULL) //栈非空
	    return S->data;//返回栈顶元素的值，栈顶指针不变		 
}




int ln(char ch)
{
	if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')
	    return 1;
	else
	    return 0;
}




//比较优先级的大小 
char Precede(char t,char ch)
{
  switch(ch)
	{
		case '(':
		{
		    return '<';
		    break;}
		case '*':
		{
			if(t=='+'||t=='('||t=='-'||t=='#')
		        return '<';
		    else
		        return '>';
		    break;}
		case '/':
		{
			if(t=='+'||t=='('||t=='-'||t=='#')
		        return '<';
		    else
		        return '>';
		    break;}
			
		case '+':
		{
			if(t=='#'||t=='(')
		        return '<';
		    else
		        return '>';
		    break;}
		case '-':
		{
			if(t=='#'||t=='(')
		        return '<';
		    else
		        return '>';
		    break;}
		case ')':
		{
			if(t!='(')
		        return '=';
		        break;}
		case '#':
		{
			if(t!='#') 
		        return '>';
		        break;}
		
	}
}

//对两个数进行运算 
int Operate(int a,char c,int b)
{
	int t;
    switch(c)
    {
        case '+':
            t=a+b;break;     
        case '-':
            t=a-b;break;
        case '*':
            t=a*b;break;
        case '/':
            t=a/b;break;        
    }
    return t;   //返回计算结果 
}


int EvaluateExpression()
{
//算术表达式求值的算法优先算法，设OPTR和OPEN分别为运算符站和操作数栈
	InitStack(OPND);//初始化open栈
	InitStack(OPTR);//初始化OPTR栈
	Push(OPTR,'#');//将表达式起始符“#”压入OPTR栈底
    char ch,theta,a,b;
    int a1,b1,t;
    cin>>ch;
	while(ch!='#' || GetTop(OPTR)!='#')//将表达式没有扫描完成的OPTR的栈顶元素不为“#”
	{   
		if(!ln(ch))
		 {//ch不是运算符则进OPND栈并读取下一个字符 
	        Push(OPND,ch);
	     	cin>>ch;}
	    else{
	        switch(Precede(GetTop(OPTR),ch))
			{			
	            case'<':
		     	{
					Push(OPTR,ch);//当前字符ch压入OPTR栈，读入下一个字符
				    cin>>ch;	
					break;}
		        case'>':
				{
					theta=Pop(OPTR);//弹出OPTR栈顶的运算符
				    a=Pop(OPND);//弹出OPND栈顶的两个运算数
				    b=Pop(OPND);
				    a1=a-'0';//将字符转化为十进制 
				    b1=b-'0';
				    Push(OPND,Operate(b1,theta,a1)+'0');//因为OPND里的数据为字符型，则再将计算结果转化为字符型
				    break; }
			    case'=':
			    {
			         a=Pop(OPND);
				     b=Pop(OPND);
				     theta=Pop(OPTR);
				     a1=a-'0';  
				     b1=b-'0'; 
					 Push(OPND,Operate(b1,theta,a1)+'0'); 
			         Pop(OPTR);//弹出OPTR栈顶的“（”，读入下一个字符ch
				     cin>>ch;
				     break;}
		     }

          }
                
      }
  printf("计算结果为：%d",GetTop(OPND)-'0');//因为OPND里的数据为字符型，则再将其转化为整型			    
}


main()
{
	printf("请输入要计算的表达式:"); 
    EvaluateExpression();
 }