栈实现的表达式计算器(c语言)

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

表达式计算器


这个东西好奇很久了


早在大一写简单的二元计算器的时候当时就想


能不能把一串表达式直接输入不是两个两个的进行计算


想半天一点思路也没有 而且不知道为什么当时也没有google


这个问题就被搁下了


前两天学数据结构的时候发现了


其中有个问题是符号匹配


突然就想起了计算器这个事


google下发现 这个东西可以用编译原理里面的词法分析和语法分析实现


也可以用数据结构里面的来实现


ok 那就试着实现一下


我的设计思路(逆向求解):


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


因此 需要将输入的中缀表达式转换为后缀表达式


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


符号需要进入符号栈进行栈运算


运算优先级高的入栈 否则弹栈 符号进入后缀表达式数组


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


将后缀表达式数组元素依次压入运算栈


遇到符号 弹两个数字 计算结果压栈


后缀表达式结束 弹出结果


需要考虑的问题


1:符号匹配


首先输入字符串的时候可以接受空格


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


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


{


例如 ((123)*3)-1+(2)


规则:


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


(1234代表数字)


}


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


例如 "1234+ 32 * ( 2 - 1)"


解决方法: 结构体


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


每个词语都有一个char的符号标记 +—/*()直接对应


数字则对应 NUMFLAG


还要说明的是:


为了让计算栈 转换栈各司其职


在调用它们之前就确保了输入的正确


如果输入的表达式中含有非数字或者非+—/*()的字母 它们会被自动忽略


例如213afd.32 + 44 44 2 -1 会变成21332+44442-1


这玩意功能还不全


例如浮点类型的输入计算


高精度的输入计算


最近看来是没时间完善了


先抻抻吧、、、



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


/**
*
* 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;
}


最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台