栈的应用——表达式求值

一、从原表达式求得后缀式

表达式存放在字符型数组str中，其后缀表达式存放在字符型数组exp中，转换过程中用一个字符型数组op作为栈。依次处理字符串str中的每个字符ch，对于每一个ch：

(1)若ch为数字，将其存放在exp中。

(2)若ch为左括弧“(”，将其压栈。

(3)若ch为右括弧“)”，将栈op中“(”上面的操作符出栈并依次存入exp中，然后“(”出栈。

(4)若ch为“+”或“-”，将op中“(”上面的所有字符(运算符)依次出栈并存入exp中，然后将ch入栈op中。

(5)若ch为“*”或“/”，将op中的栈顶连续的“*”或“/”出栈并依次存入exp中，然后将ch入栈op中。

(6)若str扫描完毕，将op中的所有运算符依次删除并存入exp中，再将ch（结束标志）存入数组exp中。

#include <iostream>
#include <conio.h>  
#define MaxSize 10

typedef struct{
	char data[MaxSize];    //存放运算符
    int top;		       //栈的最高位置
}Stack;

void trans (const char *str,  char *exp){
	Stack op;
	char ch;
	int s=0, e=0;         //e作为exp的下标, s作为str的下标
	op.top=-1;
	ch=str[s];   
	s++;

	while (ch!='\0'){         //扫描字符串
		switch(ch){    
		    case '(':	     //将ch压栈
		        op.top++;    
				op.data[op.top]=ch;  
				break;

	        case ')':	     //将op中（上面的数据依次复制到exp中
				while (op.data[op.top]!='('){  
					exp[e]=op.data[op.top];
                    op.top--;  
					e++; 
				}
		       op.top--;      //（出栈 
			   break;

			case '+':
			case '-':      //前面的运算必定都算完才算当前加减，故将栈中（前面的都出栈到exp中
				 while (op.top!=-1 && op.data[op.top]!='('){
					 exp[e]=op.data[op.top];
					 op.top--;
					 e++;
				 } 
	            op.top++;
				op.data[op.top]=ch; 
				break;

            case '*': 
            case '/':       //前面的乘除必定都算完才算当前乘除，故将栈连续的乘除都出栈到exp中
               while (op.top!=-1 && op.data[op.top]=='*' || op.data[op.top]=='/') {
				   exp[e]=op.data[op.top];
				   op.top--; 
				   e++; 
			   }
			   op.top++;   
			   op.data[op.top]=ch; 
			   break;

           case ' ':
			   break;	    //过滤掉空格

           default: 
			   while (ch>='0' && ch<='9'){        //判定为数字
	               exp[e]=ch;
				   e++;
	               ch=str[s];
				   s++;
			   }
               s--;  
			   exp[e]='#';     //用#标识一个数值串结束
			   e++; 
      }    //switch
            ch=str[s]; s++;
	}   //while

	while (op.top!=-1) {     //str扫描完毕,栈不空
        exp[e]=op.data[op.top];
        e++;
		op.top--;  
	} 
    exp[e]='\0';   //exp结束标识
} 


int main(){
	char *str="(5+6*5)+9/(5+6*5)";
   //	char *exp;
	char exp[20]="";
	std::cout<<str<<std::endl;
	trans(str,exp);
	std::cout<<exp<<std::endl;
	getch();
	return 1;
}

  运行结果：

 

(5+6*5)+9/(5+6*5)
    5#6#5#*+9#5#6#5#*+/+

 

二、后缀表达式求值
    从左到右读入后缀表达式，若读入的是一个操作数，就将它入数值栈；若读入的是一个运算符op，就从数值栈中连续出栈两个元素(两个操作数)，假设为x和y，计算x op y之值，并将计算结果入数值栈；对整个后缀表达式读入结束时，栈顶元素就是计算结果。

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 20

typedef struct {   
	float data[MaxSize];	//存放数值
	int top;		    	//栈指针
}Stack;		

float compvalue(char *exp){	 //计算后缀表达式的值
	Stack st;
    int d; 
	char ch;
	int e=0;            	//e作为exp的下标
    st.top=-1;  ch=exp[e];   e++;
    while (ch!='\0'){	    //扫描exp
		switch (ch){ 
		case '+':st.data[st.top-1]=st.data[st.top-1]+st.data[st.top];st.top--;break;
        case '-':st.data[st.top-1]=st.data[st.top-1]-st.data[st.top];st.top--;break;
        case '*':st.data[st.top-1]=st.data[st.top-1]*st.data[st.top];st.top--;break;
        case '/': 
			if (st.data[st.top]!=0){
			     st.data[st.top-1]=st.data[st.top-1]/st.data[st.top];st.top--;break;
			}else {    
				printf("\n\t除零错误!\n");
			    exit(-1);	
		    }
        default: 
			d=0;           //数值存放到d中
            while (ch>='0' && ch<='9') {  
				d=10*d+ch-'0';  
				ch=exp[e];e++; 
			}
            st.top++;  
		    st.data[st.top]=d;
		}   //case  
         ch=exp[e];  
		 e++;
	}  //while结束   
	return st.data[st.top];
} 

int main(){
	char *exp="5#6#5#*+9#5#6#5#*+/+";
	float b=compvalue(exp);
	printf("\n%f",b);
	return 1;
}

 运行结果：

35.257141