栈的应用.cpp

栈的应用

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#define maxsize 1000
#define DOUBLE_LEN 20
double stack[maxsize];
int top=-1;
void push(double value)  //进栈
{
	if(top>=maxsize)
	{
		cout<<"Stack Full"<<endl;
        exit(-1);
	}
	stack[++top]=value;
}

double pop()           //栈顶元素出栈
{
	if(top<0)
	{
		cout<<"Stack Empty"<<endl;
        return -1;          //如果栈是空的返回-1
	}
	return stack[top--];
}

int priority(int op)          //返回运算符op所对应的优先级数值
{
	switch(op)
	{
	case '*':
    case '/':
		return 3;
    case '+':
    case '-':
		return 2;
    case '(':
		return 1;
    default:
		return 0;
	}
}

int isdigit(int num)           //如果是数字
{
	if((num>=48)&&(num<=57))
		return 1;
	else if(num=='.')
		return 1;
	return 0;
}

int check(char *str)          //返回值，1是正确，0是错误
{
	int count=0;
    char c_temp=0;
    while((c_temp=*(str++))!=0)
	{
		if(c_temp=='(')
			count++;
		else if(c_temp==')')
			count--;
	}
	return (count==0?1:0);
}

int isoperator(int op)
{
	switch (op)
	{
	case '*':
    case '/':
    case '+':
    case '-':
		return 1;
    default:
        return 0;
	}
}

char *back_expression(char *mid_expression)//将中缀表达式转换为后缀表达式
{
	char c_temp=0;
    char *str_temp;
    int str_temp_pos=0;
    double stack_top_operator=0.0;/*operator on the top of stacl*/
    str_temp=(char*)malloc(maxsize);
    push((double)(';'));//把';'放入栈的底具有最底优先级
    while((c_temp=*(mid_expression++))!=0)//读如中缀表达式直到结束
	{
		if(c_temp=='(')//当运算符是'('时
			push((double)c_temp);
        else if(isdigit(c_temp))//如果读入的是数字或'.'，把它写入 str_temp
		{
			str_temp[str_temp_pos++]=c_temp;
            while(((c_temp=*(mid_expression++))!=0)&&(isdigit(c_temp)))
			{
				str_temp[str_temp_pos++]=c_temp;
			}
			mid_expression--;
            str_temp[str_temp_pos++]=' ';
		}
		else if(c_temp==')')//如果读入的是')'，运算应该出栈直到'('
		{
			while((c_temp=(int)pop())!='(')//弹出栈中所有元素直到'('
				str_temp[str_temp_pos++]=c_temp;
		}
		else if(isoperator(c_temp))//如果字符是运算符，比较优先级并决定入栈还是出栈
		{
			stack_top_operator=pop();
            while(priority((int)stack_top_operator)>=priority(c_temp))//'*','/'的优先级数是3，'+','-'的优先级数是2，否则是0
			{	str_temp[str_temp_pos++]=(int)stack_top_operator; 
                stack_top_operator=pop();
			}
			push(stack_top_operator);
            push((double)(c_temp));
		}
	}
	while((int)(stack_top_operator=pop())!=';')//弹出所有运算字符直到';'
    str_temp[str_temp_pos++]=stack_top_operator;
    str_temp[str_temp_pos]=0;
     return str_temp;
}

double cacl(char *back_expression)//将转换得到的后缀表达式求值
{
	char c_temp=0;
    double temp1=0,temp2=0;
    char str_temp[DOUBLE_LEN]={0};
    int str_temp_pos=0;
    while((c_temp=*(back_expression++))!=0)
	{
		if((isdigit(c_temp))||(c_temp=='.'))
        str_temp[str_temp_pos++]=c_temp;
        else if(c_temp==' ')
		{
			str_temp[str_temp_pos]=0;
            push(atof(str_temp));
            str_temp_pos=0;
		}
		else if(c_temp=='+')
		{
			temp2=pop();
            temp1=pop();
            push(temp1+temp2);
		}
		else if(c_temp=='-')
		{
			temp2=pop();
            temp1=pop();
            push(temp1-temp2);
		}
		else if(c_temp=='*')
		{
			temp2=pop();
            temp1=pop();
            push(temp1*temp2);
		}
		else if(c_temp=='/')
		{ 
			temp2=pop();
            temp1=pop();
            push(temp1/temp2);
		}
	}
	return pop();
}

void main()
{
	char str[20];
	cout<<"请输入中缀表达式："<<endl;
	cin>>str;
    if(check(str))
	{
		cout<<"转换成的后缀表达式为："<<endl;
		cout<<back_expression(str)<<endl;
		cout<<"计算结果为："<<endl;
		cout<<cacl(back_expression(str))<<endl;
	}
	else
		cout<<"Wrong expression"<<endl;
}