# 数据结构-栈的应用-表达式求值

## Expression Evaluation

Posted by xuepro on November 10, 2017

## ——C版本的表达式求值实现————

#include <stdio.h>
#include <malloc.h>

#define OK 0
#define ERROR 1

/*----------字符栈--------*/
typedef char EType;

typedef struct{
EType *data;
int capacity;
EType *top;
}SqStack;

int initSqStack(SqStack *pS,int size){
pS->data = (EType*)malloc(size*sizeof(EType));
if(!pS->data) return ERROR;
pS->capacity = size;
pS->top = pS->data;
return OK;
}

int pushSqStack(SqStack *pS,EType e){
if(pS->top-pS->data==pS->capacity)
return ERROR;
*(pS->top) = e;
pS->top++;
return OK;
}

int popSqStack(SqStack *pS){
if(pS->top==pS->data)
return ERROR;
pS->top--;
return OK;
}
int topSqStack(SqStack *pS,EType *e){
if(pS->top==pS->data)
return ERROR;
*e = *(pS->top-1);
return OK;
}

int isEmptySqStack(SqStack S){
if(S.top==S.data) return 1;
return 0;
}

/*----------整数栈--------*/
typedef int Type;

typedef struct{
Type *data;
int capacity;
Type *top;
}Stack;

int initStack(Stack *pS,int size){
pS->data = (Type*)malloc(size*sizeof(Type));
if(!pS->data) return ERROR;
pS->capacity = size;
pS->top = pS->data;
return OK;
}

int pushStack(Stack *pS,Type e){
if(pS->top-pS->data==pS->capacity)
return ERROR;
*(pS->top) = e;
pS->top++;
return OK;
}

int popStack(Stack *pS){
if(pS->top==pS->data)
return ERROR;
pS->top--;
return OK;
}
int topStack(Stack *pS,Type *e){
if(pS->top==pS->data)
return ERROR;
*e = *(pS->top-1);
return OK;
}

int isEmptyStack(Stack S){
if(S.top==S.data) return 1;
return 0;
}

/*----- 中缀表达式求值--- */

char op_prior_table[][7] = {
{ '>','>','<','<','<','>','>' },
{ '>','>','<','<','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '<','<','<','<','<','=','!' },
{ '>','>','>','>','!','>','>' },
{ '<','<','<','<','<','!','=' }
};

int index_of_op(const char op){
if(op=='+') return 0;
else if(op=='-') return 1;
else if(op=='*') return 2;
else if(op=='/') return 3;
else if(op=='(') return 4;
else if(op==')') return 5;
else             return 6;   /* '#' */
}

int prior(const char op1,const char op2){
int i = index_of_op(op1),j = index_of_op(op2);
char cmp = op_prior_table[i][j];
if(cmp=='>') return 1;
else if(cmp=='<') return -1;
else if(cmp=='=') return 0;
return 10000; /*不会出现的情况 */
}

/*用算符op对两个运算数进行运算 : n1 op n2 */

int op2num(const char op,int n1, int n2){
if(op=='+') return n1+n2;
//...此处补充你的代码
}

int compute_mid_expression(const char *exp){
initSqStack(&op_stack,100);
initStack(&num_stack,100);

const char *p = exp;
pushSqStack( &op_stack,'#');
while(*p!='\0'){
if( *p>='0'&&*p<='9' )  { /* 运算数 */
pushStack( &num_stack,*p-'0'); /*运算数直接入栈*/
p++;
}
else {//运算符
char op1 = topSqStack(&op_stack);
int priority =  prior(op1,*p);

if(priority==1 ){/*栈顶算符优先，需要立即弹出进行计算了*/
popSqStack(&op_stack);
/*... 加入你的代码*/
}
else if(priority==-1 ){ /*当前算符*p优先*/
pushSqStack( &op_stack,*p);
p++; /*消去栈顶，移到下一个字符 */
}
else if(priority==0 ){
/*... 加入你的代码*/
}
}
}
}

int main()
{
char *express = "3*(2+4)-8/2#";
cout<<compute_mid_expression(express)<<"\n";
return 0;
}


## ——C++(引用)版本的表达式求值实现————

#include <iostream>

#include <stack>

using namespace std;

char op_prior_table[][7] = {
{ '>','>','<','<','<','>','>' },
{ '>','>','<','<','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '<','<','<','<','<','=','!' },
{ '>','>','>','>','!','>','>' },
{ '<','<','<','<','<','!','=' }
};

int index_of_op(const char op){
if(op=='+') return 0;
else if(op=='-') return 1;
else if(op=='*') return 2;
else if(op=='/') return 3;
else if(op=='(') return 4;
else if(op==')') return 5;
else             return 6;   // '#'
}

int prior(const char op1,const char op2){
int i = index_of_op(op1),j = index_of_op(op2);
char cmp = op_prior_table[i][j];
if(cmp=='>') return 1;
else if(cmp=='<') return -1;
else if(cmp=='=') return 0;
return 10000; //不会出现的情况
}

//用算符op对两个运算数进行运算 : n1 op n2
int op2num(const char op,int n1, int n2){
if(op=='+') return n1+n2;
//...此处补充你的代码
}
int compute_mid_expression(const char *exp){
stack<char> op_stack;
stack<int> num_stack;
const char *p = exp;
op_stack.push('#');
while(*p!='\0'){
if( *p>='0'&&*p<='9' )  { /* 运算数 */
num_stack.push(*p-'0');  //运算数直接入栈
p++;
}
else {//运算符
char op1 = op_stack.top();
int priority =  prior(op1,*p);
if(priority==1 ){/*栈顶算符优先，需要立即弹出进行计算了*/
op_stack.pop();
//... 加入你的代码
}
else if(priority==-1 ){ /*当前算符*p优先*/
op_stack.push(*p); p++; /*消去栈顶，移到下一个字符(/)
}
else if(priority==0 ){
//... 加入你的代码
}
}
}
}

int main()
{
char *express = "3*(2+4)-8/2#";
cout<<compute_mid_expression(express)<<"\n";
return 0;
}