【散分】计算器完成！基本表达式都能算，公布源码：）
程序代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#include<math.h>
/*将中缀表达式转化为后缀表达式需要的数据结构*/
struct stackNode {
char data;
struct stackNode *nextPtr;
};
/*中缀转后缀*/
typedef struct stackNode StackNode;
typedef StackNode *StackNodePtr;
void luanlai(StackNodePtr *topPtr , char infix[],int j,char postfix[]) ;
void convertToPostfix(char infix[], char postfix[]);/*中缀转后缀主函数*/
int isOperator (char c);
int isNumber (char c);
int precedence (char operator1, char operator2); /*比较两个表达式的优先级*/
void push(StackNodePtr *topPtr, char value); /*将运算符压入堆栈 后进先出--中缀转后缀时所用*/
char pop (StackNodePtr *topPtr); /*将运算符弹出堆栈 后进先出--中缀转后缀时所用*/
int isEmpty (StackNodePtr topPtr);
// void printStack(StackNodePtr topPtr);
void pushNum(StackNodePtr *head, StackNodePtr *tailer, char value); /*将数字以char形式要入队列先进先出--中缀转后缀时所用*/
int popNum(StackNodePtr *head, StackNodePtr *tailer);/*将数字以int\char形式要入队列先进先出--中缀转后缀时所用*/
void printArray ( char a[]); /*打印数列*/
/*后缀表达式计算需要的数据结构*/
struct stackPostfix {
double data;
struct stackPostfix *nextPtr;
};
/*计算后缀*/
typedef struct stackPostfix StackPostfix;
typedef StackPostfix * StackPostfixPtr;
void pushPostfix(StackPostfixPtr *headPtr, double value);
double popPostfix(StackPostfixPtr *headPtr );
double evaluatePostfixExpression ( char a[]);
double calculate ( double op1 , double op2 , char operate);
void print(StackPostfixPtr headPtr); //打印堆栈
int main(void)
{
// char infix[1001]={'\0'},postfix[1001]={'\0'};
while(1)
{ //begin while
char infix[1001]={'\0'},postfix[1001]={'\0'};
printf("输入:");
gets(infix);
convertToPostfix( infix, postfix); //转换成逆波兰表达式
// printArray (postfix); 输出逆波兰表达式
printf("\n结果: %lf\n",evaluatePostfixExpression(postfix)); //计算逆波兰表达式并返回最终之
printf("\n\n");
}//end while
return 0;
}
void convertToPostfix(char infix[], char postfix[])
{
int i; /*infix末尾添加字符计数*/
int j;
StackNodePtr head=NULL; /*为记录数字链表所用，队列先进先出*/
StackNodePtr tailer=NULL; /*为记录数字链表所用,队列先进先出*/
StackNodePtr topPtr=NULL; /*堆栈,后进先出*/
char forPop[2]={0}; /*为复制堆栈所用*/
char forPopNum[2]={0}; /*为复制数字所用*/
for(i = 0; infix[i]!='\0' ; i++); /*将i移动到数组末尾*/
infix[i]=')';
infix[i+1] = '\0'; /*末尾添加) */
push(&topPtr,'(');
for (j=0; infix[j]!='\0'; j++)
{
/*如果是数字，就压入pushNum队列*/
if(isNumber(infix[j]))
pushNum(&head, &tailer, infix[j]);
/*如果是左括号，就将括号压入push堆栈，
并且在pushNum压入一个0，
确保如果是一个负数，这个负数前面有数字可减，
如果是一个正数，那么可以和任何数结合不改变大小
*/
else if(infix[j]=='(')
{
push(&topPtr,'(');
pushNum(&head,&tailer,'0');
}
/*
如果是运算符：1、首先弹出popNum队列，并且复制到postfix，循环直到队列结束。如果是负号，+ 0
2、(luanlai ()函数执行 )比较优先级，如果栈顶优先级高于当前，弹出push，复制到postfix中,否则，把弹出的运算符弹入push
3、把运算符压入pop中
*/
else if(isOperator(infix[j]))
{
while(head != NULL)
{
forPopNum[0] = popNum(&head,&tailer);
forPopNum[1] = '\0';
strcat( postfix,forPopNum );
}
strcat( postfix," "); /*压入空格*/
luanlai(&topPtr , infix,j,postfix) ;
push(&topPtr, infix[j]); /*将运算符压入堆栈*/
}
/*
如果是右括号：1、首先弹出popNum队列，并且复制到postfix，循环直到队列结束,压入空格
2、弹出运算符，复制到postfix，压入空格，直到一个左括号
3、将左括号弹出堆栈
*/
else if(infix[j]==')')
{
while(head!=NULL)
{
forPopNum[0] = popNum(&head,&tailer);
forPopNum[1] = '\0';
strcat( postfix,forPopNum);
}
strcat( postfix," ");
while( (forPop[0] = pop(&topPtr) )!= '(')
{
forPop[1]='\0';
strcat( postfix,forPop );
strcat( postfix," " );
}
}
}
}
int isOperator (char c)
{
if ( c == 43 || c == 45 || c == 42 || c == 47 || c == 94 || c == 37 )
return 1;
else
return 0;
}
int isNumber (char c)
{
if( isdigit(c) ||c==46 )
return 1;
else
return 0;
}
/*判断操作符优先级；
首先判断operator是什么运算符；
给相应的one或者two 赋值；
返回two - one 即 堆栈 - 数组中 运算符；
如果堆栈运算符优先级高于或者等于分别返回1和0，低于返回-1；
*/
int precedence (char operator1, char operator2)
{
int i;
int temp[2][2]={{operator1, operator2},{0}};
for(i = 0;i<2 ; i ++)
{
switch (temp[0][i])
{
case 43:
case 45:
temp[1][i]=1;
break;
case 42:
case 47:
case 94:
case 37:
temp[1][i]=2;
break;
case 40:
case 41:
temp[1][i]=-1;
break;
}
}
return temp[1][1]-temp[1][0];
}
/*后进先出堆栈*/
void push(StackNodePtr *topPtr, char value)
{
StackNodePtr newPtr;
if( (newPtr=(StackNodePtr) malloc (sizeof( struct stackNode) ) )!= NULL)
{
newPtr->data=value;
newPtr->nextPtr=NULL;
if( *topPtr ==NULL)
{
*topPtr=newPtr;
}
else
{
newPtr->nextPtr=*topPtr;
*topPtr=newPtr;
}
}
else
{
printf("NOT ENOUGH MEMORY\n");
}
}
char pop (StackNodePtr *topPtr)
{
StackNodePtr tempPtr;
char value;
if(*topPtr ==NULL)
{
printf("EMPTY\n");
return;
}
else
{
tempPtr = (*topPtr);
value= tempPtr->data;
(*topPtr)=(*topPtr)->nextPtr;
free(tempPtr);
return value;
}
}
void pushNum(StackNodePtr *head, StackNodePtr *tailer, char value)
{
StackNodePtr newPtr;
if( (newPtr=(StackNodePtr) malloc (sizeof( struct stackNode) ) )!= NULL)
{
newPtr->data=value;
newPtr->nextPtr=NULL;
if( *head==NULL)
{
(*head) = newPtr;
}
else
{
(*tailer)->nextPtr= newPtr;
}
(*tailer)= newPtr;
}
}
int popNum(StackNodePtr *head, StackNodePtr *tailer)
{
int value;
StackNodePtr tempPtr;
if( head !=NULL)
{
value = (*head)->data;
tempPtr = *head;
*head = (*head)->nextPtr;
free(tempPtr);
if(*head ==NULL)
*tailer=NULL;
return value;
}
}
int isEmpty (StackNodePtr topPtr)
{
if (topPtr==NULL)
return 1;
else
return 0;
}
void printArray ( char a[])
{
int i;
for (i=0; a[i]!='\0'; i++ )
printf("%c", a[i]);
}
double evaluatePostfixExpression ( char a[])
{
char b[]=" "; /*strtoken的条件*/
char *token;
StackPostfixPtr headPtr=NULL;
double x=0.00;
double y=0.00;
token = strtok( a, b);
while (token != NULL)
{
if(isNumber( *token ) )
{
pushPostfix( &headPtr, atof(token) );
}
else
{
x=popPostfix( &headPtr );
y=popPostfix( &headPtr );
pushPostfix(&headPtr,calculate( x , y , (*token) ) );
}
token =strtok (NULL , b);
}
return popPostfix(&headPtr);
}
void pushPostfix(StackPostfixPtr *headPtr, double value)
{
StackPostfixPtr newPtr;
if( (newPtr=(StackPostfixPtr) malloc (sizeof( struct stackPostfix) ) )!= NULL)
{
newPtr->data=value;
newPtr->nextPtr= *headPtr;
*headPtr = newPtr;
}
else
{
printf("NOT ENOUGH MEMORY\n");
}
}
double popPostfix(StackPostfixPtr *headPtr )
{
StackPostfixPtr tempPtr;
double value;
if( (*headPtr) ==NULL)
{
return 0;
}
else
{
tempPtr = (*headPtr);
value= tempPtr->data;
(*headPtr)=(*headPtr)->nextPtr;
free(tempPtr);
return value;
}
}
double calculate ( double op1 , double op2 , char operate)
{
switch (operate)
{
case 43:
return op1+op2;
case 45:
return op2-op1;
case 42:
return op2*op1;
case 47:
return (double)op2/op1;
case 94:
return pow(op2,op1);
case 37:
return (int)(op2)%(int)(op1);
}
return 0;
}
void luanlai(StackNodePtr *topPtr , char infix[],int j,char postfix[])
{
char forPop[2]={'\0'};
forPop[0] = pop(topPtr);
forPop[1]='\0';
if( (precedence(infix[j], forPop[0]))==1 || (precedence(infix[j], forPop[0]))==0)
{
strcat( postfix,forPop );
strcat( postfix," ");
/*压入空格*/
luanlai(topPtr , infix,j,postfix) ;
}
else
push( topPtr, forPop[0]);
}
void print(StackPostfixPtr headPtr)
{
if(headPtr ==NULL)
{
printf("empty");
}
else
{
printf("\nthe stack is:\n");
while(headPtr !=NULL)
{
printf( "%lf-->", headPtr->data);
headPtr=headPtr->nextPtr;
}
}
printf("NULL\n\n");
}
