# 栈实现的表达式计算器（c语言）

2016-12-14 09:56:25来源:http://blog.csdn.net/duoduo3_69/article/details/6895976作者:duoduo3_69人点击

ok 那就试着实现一下

>>首先 我选择的是逆波兰式解法

>>此处需要一次栈运算： 数字直接进入后缀表达式的数组

>>转换完毕后进行运算 此时需要一个运算栈

1：符号匹配

>>第一次判断：括号个数匹配

>>第二次判断：符号匹配

{

1234 后 +-/* )
+-*/ 后 1234 (
( 后 1234 (
) 后 +-/* )

（1234代表数字）

}

2:如何将字符串转换成可以处理的字符

`#define NUMFLAG '@'`
`typedef struct tokenNode{	char opr;	double data;}tokenNode;`

╮(╯▽╰)╭ 不说了 最后把代码贴上吧

`/** * * dynamic size * stack * * this calculator only take + - * / * this calculator only take short precision * only take number in int not double * if input charactor without the set of +-/*()number the charactor will be ignored * @version 1.01 * @author  yangyang * 2011 10 22 * * * */#include#include#include#define BOTTOM 0#define BOOL int#define TRUE 1#define FALSE 0#define NUMFLAG '@'/* the opr is a flag  */typedef struct tokenNode{	char opr;	double data;}tokenNode;/* actually a sentence */typedef tokenNode* Token;typedef struct tokenStack{	Token token;	int size;	int top;}tokenStack;typedef tokenStack* Stack;Stack newStack(int size){	Stack L = (Stack)malloc(sizeof(tokenStack));	L->token = (Token)malloc(size * sizeof(tokenNode));	L->top = 0;	L->size = size;	return L;}BOOL isEmpty(Stack L){	if(BOTTOM >= L->top)	{		return TRUE;	}	return FALSE;}BOOL isFull(Stack L){	if(L->size <= L->top)	{		return TRUE;	}	return FALSE;}BOOL push(Stack L,tokenNode node){	if(isFull(L))	{		printf("The Stack Is Full!!!/n");		return FALSE;	}	++L->top;	L->token[L->top].opr = node.opr;	L->token[L->top].data = node.data;	return TRUE;}BOOL pop(Stack L){	if(isEmpty(L))	{		printf("The Stack Is Empty!!!/n");		return FALSE;	}	--L->top;	return TRUE;}char getTopOpr(Stack L){	return L->token[L->top].opr;}double getTopData(Stack L){    return L->token[L->top].data;}void deleteStack(Stack L){	L->top = 0;	L->size = 0;	free(L->token);	L->token = NULL;	free(L);	L = NULL;}/* in order not to waste space new a Token before Stack */Token newToken(size){	if(0 == size)	{		return NULL;	}	Token L = (Token)malloc(size*sizeof(tokenNode));	return L;}void deleteToken(Token L){    free(L);    L = NULL;}/* this will translate string to Token */void stringToToken(char str[],int str_length, Token L){	BOOL preint = FALSE;	int i,j = 0,sum = 0;	for(i = 0; i < str_length; i++)	{		if(str[i] >= '0' && str[i] <= '9')		{			if(FALSE == preint)			{				sum = 0;				preint = TRUE;			}			sum = sum * 10 + str[i] - '0';		}		else		{			if(TRUE == preint)			{				L[j].opr = NUMFLAG;				L[j].data = sum;				preint = FALSE;				++j;			}			switch(str[i])			{				case '+':				case '-':				case '*':				case '/':				case '(':				case ')':						 L[j].opr = str[i];						 ++j;						 break;				default:continue;			}		}	}	/* if last element if a num */	if(str[str_length-1] >= '0' && str[str_length-1] <= '9')	{        if(TRUE == preint)        {            L[j].opr = NUMFLAG;            L[j].data = sum;            preint = FALSE;        }	}}/* this will return the tokennode's num of a string *//* exp: (3333+3 ) - 3 * 4 equ (3333+3)-3*4 return 9 */int sizeElementExpresion(char str[]){    int sz_element = 0,i;    int flag_preint = FALSE;    for(i = 0; str[i] != '/0'; i++)    {        if(str[i]>='0' && str[i]<='9')        {            if(FALSE == flag_preint)            {                flag_preint = TRUE;                ++sz_element;            }            continue;        }        else        {            switch(str[i])            {                case '+':                case '-':                case '*':                case '/':                case '(':                case ')':                         ++sz_element;                         flag_preint = FALSE;                         break;                default:continue;            }        }    }    return sz_element;}void printToken(Token L,int len){    int i = 0;    for(; i < len; i++)    {        if(NUMFLAG != L[i].opr)        {            printf("%c",L[i].opr);        }        else        {            printf("%lf",L[i].data);        }    }}void printStack(Stack suffixstack){    int i = 1;    for(; i <= suffixstack->top; i++)    {        if(NUMFLAG != suffixstack->token[i].opr)        {            printf("%c",suffixstack->token[i].opr);        }        else        {            printf("%lf",suffixstack->token[i].data);        }    }    printf("/n");}/* take token to suffix token */Stack changeToSuffixStack(Token token,int len){    /* only need push */    Stack sufstack = newStack(len);    /* symbol need stack operate */    Stack symbolstack = newStack(len);    int i;//,j = 0;    for(i = 0; i    {        /* a number */        if(NUMFLAG == token[i].opr)        {            push(sufstack,token[i]);        }        /* a symbol */        else        {            if(isEmpty(symbolstack))            {                push(symbolstack,token[i]);                continue;            }            /* ) */            if('('== token[i].opr)            {                push(symbolstack,token[i]);                continue;            }            if(')' == token[i].opr)            {                while('(' != symbolstack->token[symbolstack->top].opr)                {                    tokenNode p;                    p.opr = getTopOpr(symbolstack);                    push(sufstack,p);                    pop(symbolstack);                }                pop(symbolstack);                continue;            }            switch(symbolstack->token[symbolstack->top].opr)            {                case '(':push(symbolstack,token[i]);                         break;                case '*':                case '/':push(sufstack,symbolstack->token[symbolstack->top]);                         pop(symbolstack);                         --i;                         continue;                         break;                case '+':                case '-':                         {                         if('+' == token[i].opr || '-' == token[i].opr)                          {                            push(sufstack,symbolstack->token[symbolstack->top]);                            pop(symbolstack);                            push(symbolstack,token[i]);                            break;                          }                         if('*' == token[i].opr || '/' == token[i].opr)                         {                            push(symbolstack,token[i]);                            break;                         }                         break;                        }            }        }    }    if(NUMFLAG == token[len-1].opr || ')' == token[len-1].opr)    {        while(!isEmpty(symbolstack)&&              '(' != symbolstack->token[symbolstack->top].opr)        {            push(sufstack,symbolstack->token[symbolstack->top]);            pop(symbolstack);        }    }    return sufstack;}double calculate(Stack suffix){    int i,len = suffix->top;    Stack calstack = newStack(len);    /* result = op1 / op2 */    tokenNode p;    double result = 0,op_1,op_2;    /* forget why 1 first ... */    for(i=1; i<=len; i++)    {        if(NUMFLAG == suffix->token[i].opr)        {            push(calstack,suffix->token[i]);        }        else        {            op_2 = getTopData(calstack);            pop(calstack);            op_1 = getTopData(calstack);            pop(calstack);            switch(suffix->token[i].opr)            {                case '+':result = op_1 + op_2;                         break;                case '-':result = op_1 - op_2;                         break;                case '/':result = op_1 / op_2;                         break;                case '*':result = op_1 * op_2;                         break;            }            p.data = result;            p.opr = NUMFLAG;            push(calstack,p);        }    }    result = calstack->token[calstack->top].data;    deleteStack(calstack);    return result;}/* check expreesion  brace number is correct or not such as (()  )((*/BOOL braceNumberCorrect(char s[]){    int left = 0, right = 0;    char *p = s;    while(*p != '/0')    {        if(*p == '(')        {            left++;        }        if(*p == ')')        {            right++;        }        ++p;    }    if(left == right)    {        return TRUE;    }    return FALSE;}/* check token expression is correct or not  */BOOL tokenExpressionCorrect(Token sentence,int len){    int i = 0;    /* token[i+1] i+1 < len */    if(sentence[len-1].opr == NUMFLAG       || sentence[len-1].opr == ')')    {        ;    }    else    {        return FALSE;    }    for(; i    {        switch(sentence[i].opr)        {            case NUMFLAG:                         if(sentence[i+1].opr == ')'                         ||sentence[i+1].opr == '+'                         ||sentence[i+1].opr == '-'                         ||sentence[i+1].opr == '/'                         ||sentence[i+1].opr == '*')                         {                            continue;                         }                         else                         {                            return FALSE;                         }                         break;            case ')':                     if(sentence[i+1].opr == ')'                        ||sentence[i+1].opr == '+'                        ||sentence[i+1].opr == '-'                        ||sentence[i+1].opr == '/'                        ||sentence[i+1].opr == '*')                        {                            continue;                        }                         else                        {                            return FALSE;                        }                     break;            case '-':            case '/':            case '*':            case '+':            case '(':                     if(sentence[i+1].opr == '('                        ||sentence[i+1].opr == NUMFLAG)                    {                        continue;                    }                         else                    {                        return FALSE;                    }                     break;        }    }    return TRUE;}/* only take 1~9 + - / * ( )  */void changeToCorrectExpression(char str[],int len){    char p[len+1];    int i, j = 0;    for(i = 0; i < len ; i++)    {        if(str[i] >= '0' && str[i] <= '9')        {            p[j++] = str[i];            continue;        }        else        {        switch(str[i])        {            case '+':            case '-':            case '/':            case '*':            case '(':            case ')':                     p[j++] = str[i];                     break;        }        }    }    p[j] = '/0';    strcpy(str,p);    return ;}int main(){    char s[100];    char EXIT[] = "000";    int expression_length,str_length;    printf(">this calculator onle take short precision/n");    printf(">if input charactor without the set of +-/*()number the charactor will be ignored/n");    printf(">please input like this (33 - 2 )/11 /n");    printf("-> ");    while(gets(s))    {        if(!strcmp(EXIT,s))        {            exit(0);        }        if(!braceNumberCorrect(s))        {            printf("brace number is incorrect/n");            printf("-> ");            continue;        }        changeToCorrectExpression(s,strlen(s));        expression_length = sizeElementExpresion(s);        Token sentence = newToken(expression_length);        str_length = strlen(s);        stringToToken(s,str_length,sentence);        if(tokenExpressionCorrect(sentence,expression_length))        {            //printToken(sentence,expression_length);            ;        }        else        {            printf("input error/n");            printf("-> ");            continue;        }        Stack suffixstack = changeToSuffixStack(sentence,expression_length);        if(NULL != suffixstack)        {//            printToken(sentence,expression_length);            printf(" = %lf/n",calculate(suffixstack));            deleteStack(suffixstack);        }        deleteToken(sentence);        printf("-> ");    }	return 0;}`