博客

完整代码

#include<stdio.h>                      
#include<malloc.h>                      
#include<limits.h>                      
#include<string.h>                       
#include<stdlib.h>                       
#include<io.h>                           
#include<math.h>                         
#include<process.h>                     



typedef struct {
	char S[20];
	int top;
}CHARStack;

//初始化栈 
void InitStack(CHARStack *S) {
     S->top = -1;
}

//入栈 
void Push(CHARStack *S, char ch) {
	if (S->top >= 19) {
		printf("栈满!\n");
		exit(0);
	}
	else {
		S->top++;
		S->S[S->top] = ch;
	}
}

//获取栈顶元素 
char GetTop(CHARStack* S) {
	if (S->top==-1) {
		printf("栈空!\n");
		exit(0);
	}
	else {
		
		return S->S[S->top];
	}
}

//判断是否为数值型字符 
int TRIn(char ch) {                           
	if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || ch == '#') {
		return 0;
	}
	else return 1;
}


//运算符优先级判断 
char Precede(char ch1, char ch2) {
	if (ch1 == '+') {
		if (ch2 == '+')return '>';
		if (ch2 == '-')return '>';
		if (ch2 == '*')return '<';
		if (ch2 == '/')return '<';
		if (ch2 == '(')return '<';
		if (ch2 == ')')return '>';
		if (ch2 == '#')return '>';
	}
	else if (ch1 == '-') {
		if (ch2 == '+')return '>';
		if (ch2 == '-')return '>';
		if (ch2 == '*')return '<';
		if (ch2 == '/')return '<';
		if (ch2 == '(')return '<';
		if (ch2 == ')')return '>';
		if (ch2 == '#')return '>';
	}
	else if (ch1 == '*') {
		if (ch2 == '+')return '>';
		if (ch2 == '-')return '>';
		if (ch2 == '*')return '>';
		if (ch2 == '/')return '>';
		if (ch2 == '(')return '<';
		if (ch2 == ')')return '>';
		if (ch2 == '#')return '>';
	}
	else if (ch1 == '/') {
		if (ch2 == '+')return '>';
		if (ch2 == '-')return '>';
		if (ch2 == '*')return '>';
		if (ch2 == '/')return '>';
		if (ch2 == '(')return '<';
		if (ch2 == ')')return '>';
		if (ch2 == '#')return '>';
	}
	else if (ch1 == '(') {
		if (ch2 == '+')return '>';
		if (ch2 == '-')return '>';
		if (ch2 == '*')return '>';
		if (ch2 == '/')return '>';
		if (ch2 == '(')return '>';
		if (ch2 == ')')return '=';
		if (ch2 == '#') {
			printf("输入的多项式有误!\n");
			exit(0);
		}
	}
	else if (ch1 == ')') {
		if (ch2 == '+')return '>';
		if (ch2 == '-')return '>';
		if (ch2 == '*')return '>';
		if (ch2 == '/')return '>';
		if (ch2 == '(') {
			printf("输入的多项式有误!\n");
			exit(0);
		}
		if (ch2 == ')')return '>';
		if (ch2 == '#')return '>';
	}
	else if (ch1 == '#') {
		if (ch2 == '+')return '<';
		if (ch2 == '-')return '<';
		if (ch2 == '*')return '<';
		if (ch2 == '/')return '<';
		if (ch2 == '(')return '<';
		if (ch2 == ')') {
			printf("输入的多项式有误!\n");
			exit(0);
		}
		if (ch2 == '#')return '=';
	}
	else {
		printf("出错！");
		exit(0);
		return 0;
	}
}

//出栈 
void Pop(CHARStack* S, char* ch) {
	if (S->top == -1) {
		printf("栈空!\n");
		exit(0);
	}
	else {
		*ch=S->S[S->top];
		S->top--;
	}
}

//将数值型字符转化为int类型 
int changchartonumber(char ch) {
	if (ch == '0') {
		return 0;
	}
	else if (ch == '1') {
		return 1;
	}
	else if (ch == '2') {
		return 2;
	}
	else if (ch == '3') {
		return 3;
	}
	else if (ch == '4') {
		return 4;
	}
	else if (ch == '5') {
		return 5;
	}
	else if (ch == '6') {
		return 6;
	}
	else if (ch == '7') {
		return 7;
	}
	else if (ch == '8') {
		return 8;
	}
	else if (ch == '9') {
		return 9;
	}
	else {
		
		return (int)ch;
		
	}
}

//逆波兰式求值 
char Operate(char ch1, char theta, char ch2) {
	int c1, c2;
	c1 = changchartonumber(ch1);
	c2 = changchartonumber(ch2);
	
	if (theta == '+') {
		return c1 + c2;
	}
	else if (theta == '-') {
		return c1 - c2;
	}
	else if (theta == '*') {
		return  c1 * c2;
	}
	else if (theta == '/') {
		return c1 / c2;
	}
	else {
		printf("错误");
		exit(0);
		return '0';
	}

}

int main() {
	char c,theta,a,b,xl,p,i,t[15]={0};
	i=0;
	CHARStack *OPTR , *OPER;                     
	OPTR = (CHARStack*)malloc(sizeof(CHARStack));
	OPER = (CHARStack*)malloc(sizeof(CHARStack));
	InitStack(OPTR);
	InitStack(OPER);
	Push(OPTR,'#');
	c = getchar();
	while (c != '#') {
		if (TRIn(c)) {  
		    t[i]=c;
			i++;            
			c = getchar();
		}
		else 
	 	{
			switch (Precede(c,GetTop(OPTR)))
			{
	            case'<':
				   Pop(OPTR,&p);
				   if(p!='('&&p!=')')
				       {
				       	    t[i]=p;
				       	    i++;
					   }
					   Push(OPTR,c);
					   c=getchar();
					   break;
				case'=':
					Pop(OPTR,&p);
					Push(OPTR,c);
					if(p!='('&&p!=')'&&GetTop(OPTR)!='#')
					    {
					    	t[i]=p;
					    	i++;
						}
					c=getchar();
					break;
				case'>':
					Push(OPTR,c);
					c=getchar();
					break;				
			}
		}
	}
	while (GetTop(OPTR) != '#') 
	    {  
		    Pop(OPTR, &p);
	    	if(p!='('&&p!=')')
	    	{
	    	    t[i]=p;
	    	    i++;
			}
	    	
		}
	i=0;
	while(t[i]!=0)
	    {
	    	if(TRIn(t[i]))
	    	    {
	    	    	Push(OPER,t[i]);
	    	    	i++;
				}
			else
			    {
			    	Pop(OPER,&a);
			    	Pop(OPER,&b);
			    	Push(OPER,Operate(b,t[i],a));
			    	i++;
				}
		}
	printf("逆波兰式:%s\n",t);
	printf("结果为:%d",OPER->S[OPER->top]);
	return 0;
}