数据结构 简单算式表达式求值

利用栈实现的简单中缀表达式求值（C语言）

这只是个小做业，要求实现简单中缀表达式求值code

所谓前缀、中缀、后缀，是指运算符相对于运算数的位置而言，看以下例子：内存

(1 + 2) × 3 - 4   就是中缀表达式
- × + 1 2 3 4     就是前缀表达式
1 2 + 3 × 4 -     就是后缀表达式rem

因此其实只有加、减、乘、除以及括号的四则运算，大体思路是定义了两个栈：操做符栈和操做数栈，顾名思义，操做符用于存放运算符，操做数用于存放运算数字。代码以下：it

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
/**
* 操做栈的相关定义 
*/
typedef struct 
{
	char *elem;
	int top;
	int size;
 }Sqstack;
 //定义操做符栈和操做数栈 
 Sqstack Ope;
 Sqstack Num;
 
 void Initstack(Sqstack *s) //初始化栈 
 { 
    s->size=50;
    s->top=0;  
    s->elem=(char*)malloc(s->size*sizeof(char));
    if(!s->elem)  
        printf("OVERFLOW");
 }

 void Push(Sqstack *s,char e)  //入栈
 {
 	 if(s->top>=s->size)//栈内存不够时
	 {
	 	char *newelem;
	 	int increment=50;
	 	newelem=(char*)realloc(s->elem,(s->size+increment)*sizeof(char));
	 	s->elem=newelem;
	 	s->size=s->size+increment;
	  } 
	 s->elem[s->top]=e;
	 s->top++; 
 }
 
void Pop(Sqstack *s)//出栈 
{
   s->top--;
}
 
char GetTop(Sqstack *s)//取栈顶元素
{
	char e;
	s->top--;
	e=s->elem[s->top];
	
	return e;
}
void calculate(Sqstack *ope,Sqstack *num)
{  
  
    char num1,num2,op; 
    num2=GetTop(num);  
    num1=GetTop(num);  
    op=GetTop(ope);
    int tmpResult=0;  
    switch(op)
	{  
        case '+':  
            tmpResult=num1+num2;            
            break;  
        case '-':  
            tmpResult=num1-num2;  
            break;  
        case '*':  
            tmpResult=num1*num2;  
            break;  
        case '/':  
            tmpResult=num1/num2;  
            break;  
    }  
    Push(num,tmpResult);//入栈   
}   
void dealExpression()
{   
    Initstack(&Ope);
    Initstack(&Num);
    printf("请输入正确的中缀表达式(以#号结束)：");  
    char onechar; //单个字符 
    scanf("%c",&onechar);  
    while(onechar!='#')
	{  
        switch(onechar)
		{  
            case '+':  
            case '-':  
                if(Ope.top&&Ope.elem[Ope.top-1]!='(')
				{  
                    calculate(&Ope,&Num);  
                }  
                Push(&Ope,onechar); //入栈 
                scanf("%c",&onechar);  
                break;  
            case '*':  
            case '/':  
                if(Ope.top&&(Ope.elem[Ope.top-1]=='*'||Ope.elem[Ope.top-1]=='/'))
				{  
                    calculate(&Ope,&Num);  
                }  
				Push(&Ope,onechar); //入栈 
                scanf("%c",&onechar);  
                break;  
            case '(':  
                Push(&Ope,onechar); //入栈 
                scanf("%c",&onechar);  
                break;  
            case ')':  
                while(Ope.elem[Ope.top-1]!='(')//当前是')'，则Ope栈必定能有'('匹配到,即Ope栈必定不为空 
				{                                  
                    calculate(&Ope,&Num);  
                }  
                Pop(&Ope);//出栈，弹出左括号  
                scanf("%c",&onechar);  
                break;  
            default://onechar为数字，则入num栈  
                char opNum=0;  
                do{  
                    opNum=opNum*10+onechar-'0';  
                    scanf("%c", &onechar);  
                }while(onechar>='0' && onechar<='9');  
                Push(&Num,opNum); 
                break;  
        }//end switch  
    }//end while  
    while(Ope.top)
	{  
        calculate(&Ope,&Num);  
    }  
    int result;
	result=Num.elem[Num.top-1];  
    printf("计算结果是%d\n", result);  
}  
int main()
{  
    dealExpression();
	return 0;  
}