表达式求值是栈这种数据结构的一个很经典的应用，恰逢是数据结构期末实践题目，经过一定的努力终于也是实现了这个算法，所以分享下我的思路和经验，希望正准备尝试解决这个问题的同学可以少走些弯路，有所借鉴和收获。

个人水平有限，文笔拙劣，有所意见和建议欢迎指出

我们日常使用的四则运算式如 1+1 被称为中缀表达式，即所有的运算符号都在运算数的中间出现，我们在初学编程时都练习过简单的二元运算，但当求值问题扩大到一个完整的四则运算式的时候，就需要考虑运算符优先级、括号等多个问题，解决了这些问题也就实现了表达式求值。

表达式求值问题常用的也是最广泛的解决方法是逆波兰式转换法，主要步骤可简单分为两步，用户输入的中缀表达式转化为后缀表达式（逆波兰式），再对逆波兰式进行运算。但在编程过程中我发现简单的分为两步是行不通的，因为涉及到多位数和浮点数，由于输入时统一存储为字符串，在进行中缀到后缀的转换后无法得到正确的后缀式字符串，由于c语言中char型数据实际上也是int型数据，这就进一步增加了正确转换的难度，从而也就无法在逆波兰式的计算中得出正确的结果，所以在编程实现时将这两步合为一个函数实现，即以字符串形式存储键盘输入的表达式后，对该字符串逐位处理，通过ASCII码值的判断分为数字或小数点、运算符两种情况，然后按照判断结果执行相应的语句。

准备工作

创建一char型数组用于存储输入的中缀表达式，在中缀表达式向后缀表达式的转化以及后缀表达式的计算中（详情见各种数据结构教材或书籍，或相关博客，实现此算法必须要实现了解这些过程）我们知道，因为涉及到运算符优先级的判断和后缀表达式的计算的部分我们需要借助栈来实现，所以需要创建一double型栈和一char型栈，分别用于存储操作数和运算符，栈的存储可随意选用线性结构或链式结构，需要实现以下操作函数：

• 初始化
• 出栈
• 入栈
• 取栈顶
• 判空

接下来对如何处理输入的表达式做详细介绍

1.数字或小数点（非运算符）

上图为ASCII码对照表

通过ASCII码我们可以得出输入的是数字（0-9）的条件，但因为存在多位数的情况，所以当前数字可能是输入的操作数的十位或百位等，所以不能简单的压入数字栈就完事，我的解决方法是每当遇到数字位都进行一次判断，检查表达式字符串中它的前一位是否为数字，若是，则说明这是个多位数，则将前一位（已入栈）出栈与10的n次幂做乘积后与当前位求和再入栈；对于例如12.34这类浮点数，则在判断当前位不是运算符后首先检查是否为小数点，若是则说明直到下一个运算符都是该浮点数的小数位，则与求多位整数（例12.34的整数位）值类似，与10的负n次幂做乘积累加求和知道遇到下一个运算符时入栈。

上图是我做的流程图（第一次做，略丑，希望能帮助理解即可）

2.运算符

运算符的处理相对于操作数就简单许多了，唯一的小问题就是运算符优先级的判断，我第一次写的时候写了层层嵌套的if和switch语句，做了简化修改后可以这样写：

char Precede(char c1,char c2){
	//判定运算符的栈顶运算符与读入的运算符之间优先关系
    char c;
    switch(c1){
        case '+':
        case '-':
	    	switch(c2){
		        case '+':
	            case '-':
		        case ')':
	            case '#':
			    	c='>';
	               	break;
		        default:
			    	c='<';
	    	}
        	break;
        case '*':
        case '/':
            if(c2=='('){
				c='<';
			}
			else{
				c='>';
			}
            break;
        case '(':
		    if(c2==')'){
				c='=';
			}
		    else{
				c='<';
			}
            break;
        case ')':
	    	c='>';
            break;
        case '#':
		    if(c2=='#'){
				c='=';
			}
		    else{
				c='<';
			}
    }
    return c;
}

解决了优先级的判断问题后，根据中缀转后缀的步骤，优先级高于栈顶入栈，低的出栈运算直到栈顶元素优先级低于当前位，思路如下：

 

如上所述，对表达式字符串处理完毕后，此时运算结果其实就是操作数栈的栈顶元素，且操作数栈仅剩该数字，输出即可。

下面是完整代码和流程图，如果文字描述不足以让你彻底明白这个问题的解决方法，希望能静下心多看看代码，愿你能保持学习的热情

//[email protected] 12/18
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define MAXSIZE 100
//double栈，用于存放运算数 
typedef struct {
	double data[MAXSIZE];
	int top;
}Stack_n;
//char栈，用于存放运算符
typedef struct {
	char data[MAXSIZE];
	int top;
}Stack_c;
//栈的初始化
void Init_n(Stack_n s);
void Init_c(Stack_c s);
栈的判空函数
int IsEmpty_n(Stack_n s);
int IsEmpty_c(Stack_c s);
//入栈函数 
void Push_n(Stack_n *s,double e);
void Push_c(Stack_c *s,char e);
//出栈函数
void Pop_n(Stack_n *s,double *e);
void Pop_c(Stack_c *s,char *e);
//取栈顶函数
double GetTop_n(Stack_n s);
char GetTop_c(Stack_c s);

char Precede(char c1,char c2);//判断优先级 
double Operate(double a,char theta,double b);//二元运算 
int In(char c,char *OP);//是否为 + - * / ( ) 
void check(char *s);//用于检查输入的多项式格式是否正确
double Poland(char * s);//主要功能实现函数

char OP[7]={'+','-','*','/','(',')','#'}; //运算符数组(因多个函数使用故声明为公有的)

int main(){
	char s[100];
	printf("请输入表达式：\n");
	gets(s);
	double r = Poland(s);
	printf("%1.2lf\n",r);
	return 0;	
}

void Init_n(Stack_n *s){
	s->top = 0;
}

void Init_c(Stack_c *s){
	s->top = 0;
}
//栈的判空函数
int IsEmpty_n(Stack_n s){
	if(s.top == 0){
		return 1;
	}
	else{
		return 0;
	}
}
int IsEmpty_c(Stack_c s){
	if(s.top == 0){
		return 1;
	}
	else{
		return 0;
	}	
}
//入栈函数 
void Push_n(Stack_n *s,double e){
	s->top++;
	s->data[s->top] = e;
}
void Push_c(Stack_c *s,char e){
	s->top++;
	s->data[s->top] = e;
}
//出栈函数
void Pop_n(Stack_n *s,double *e){
	*e = s->data[s->top];
	s->top--;
}
void Pop_c(Stack_c *s,char *e){
	*e = s->data[s->top];
	s->top--;
}
//取栈顶函数
double GetTop_n(Stack_n s){
	return s.data[s.top];
}
char GetTop_c(Stack_c s){
	return s.data[s.top];
}

char Precede(char c1,char c2){
	//判定运算符的栈顶运算符与读入的运算符之间优先关系
    char c;
    switch(c1){
        case '+':
        case '-':
	    	switch(c2){
		        case '+':
	            case '-':
		        case ')':
	            case '#':
			    	c='>';
	               	break;
		        default:
			    	c='<';
	    	}
        	break;
        case '*':
        case '/':
            if(c2=='('){
				c='<';
			}
			else{
				c='>';
			}
            break;
        case '(':
		    if(c2==')'){
				c='=';
			}
		    else{
				c='<';
			}
            break;
        case ')':
	    	c='>';
            break;
        case '#':
		    if(c2=='#'){
				c='=';
			}
		    else{
				c='<';
			}
    }
    return c;
}

double Operate(double a,char theta,double b){
	//进行二元运算 a theta b
	double sum;
    switch(theta)
    {
       case '+':
	   sum=a+b;
	   break;
       case '-':
	   sum=a-b;
	   break;
       case '*':
           sum=a*b;
           break;
       case '/':
           sum=a/b;
	   break;
    }
    return sum;
}

int In(char c,char *OP){
    //判断是不是运算符
    for(int i=0;i<7;i++)
       if(c==OP[i])   //是运算符
          return 1;
    return 0;
}
//判断思路：当前字符是运算符且前一位或后一位也是运算符且这3位都不为‘（’和‘）’时说明连续输入了两个运算符
void check(char *s){
	char *t = s;
	for(int i = 0;i < strlen(s);i++){
		if(i > 0 && i < strlen(s) - 1 && In(s[i],OP) && (In(s[i - 1],OP) || In(s[i + 1],OP))
			&&(s[i] != '(' && s[i] != ')') && (s[i - 1] != '(' && s[i - 1] != ')')
			&&(s[i + 1] != '(' && s[i + 1] != ')')){
			printf("输入格式有误！！请检查是否存在连续输入了运算符等错误！！\n");
			getchar();
			exit(0);
		}
	}
}

double Poland(char * s){
	//对多项式格式进行检查
	check(s);
    //进行多项式的求值以及后缀表达式的输出
    int i=0,len,flag=0;
    double a,b,sum;
    char c1=s[0],e;
    
    Stack_c OPTR; 	//运算符栈
    Stack_n OPND; 	//运算数栈
    Init_c(&OPTR);  //初始化栈
    Init_n(&OPND);
    
    len=strlen(s);
    s[len]='#';
    s[len+1]='\0';
    Push_c(&OPTR,'#');//补‘#’作为结束标志
    while(s[i]!='#'||GetTop_c(OPTR)!='#'){ //遍历每一个字符 为‘#’结束循环
		if(s[i] == ' '){
			i++;
			continue;
		}
        if(!In(s[i],OP)){ //如果不是运算符
	        if(c1=='.'){//如果上一个字符是小数点
		        flag++;
		    }
		    if(flag){
		    	double t;
		    	Pop_n(&OPND,&t);
				Push_n(&OPND,t + (double)(s[i] - '0') / pow(10,flag));//对小数点后的部分 按位数运算并入栈 
				flag++;
			}
	        if(s[i]!='.'&&!flag){
	            if(!In(c1,OP)&&!IsEmpty_n(OPND)){//如果上一个字符是数字（说明是多位数） 根据位数运算后入栈
	            	double t;
	            	Pop_n(&OPND,&t);
	                Push_n(&OPND,t * 10 + s[i] - '0');
	            }
	            else//否则压入运算数栈
	            	Push_n(&OPND,(double)(s[i]-'0'));
		    }
	    	c1=s[i++]; //读取下一个字符
	    }
        else{//如果是运算符
            flag=0;
            switch(Precede(GetTop_c(OPTR),s[i])){
                 case '>':  //当前运算符优先级低
		             Pop_c(&OPTR,&e); //运算符出栈,和操作数的头两个数运算 
		             Pop_n(&OPND,&b);
                     Pop_n(&OPND,&a);
		             Push_n(&OPND,Operate(a,e,b)); //计算结果入栈
                     break;
                 case '=': //优先级相等
		             Pop_c(&OPTR,&e); //弹出运算符栈顶元素
		             c1 = s[i++];
                     break;
                 case '<':
		          	Push_c(&OPTR,s[i]); //当前运算符优先级高 入栈
		            c1 = s[i++];
                    break;
	    	}
        }
    }
    sum=GetTop_n(OPND);
    return sum; //返回运算数栈顶元素，即运算结果 
}//@@ end @@

代码也是看了很多博客帖子后总结出来的，建议好好利用搜索引擎。

栈的实现、逆波兰转换和计算等基本概念很多书都有，我看的是学校教材，清华大学出版社出版、严蔚敏老师的《数据结构（C语言版）》和程杰老师的《大话数据结构》。