中缀表达式计算器源代码,数据结构与算法,技术交流,鱼C论坛

Leo-Yeo 发表于 2015-8-24 00:33:07

中缀表达式计算器源代码

我试过几种方法，可是怎么也无法把小甲鱼所讲的逆波兰计算器和中缀转换成逆波兰计算器的源代码正确的结合在一起，求大神解决

无名侠 发表于 2015-8-24 11:00:53

{:7_122:}只有自己写过才能发现问题。

牡丹花下死做鬼 发表于 2015-8-24 13:22:38

为什么不行呢？

顺⑦zi然 发表于 2015-12-31 14:47:00

我也在想这个问题楼主解决了可以分享给我吗？

maoyu 发表于 2016-9-10 11:46:17

学习学习

lb2616 发表于 2016-11-12 21:14:53

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
#include<ctype.h>

#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
#define MAXBUFFER 10

char string;

typedef char ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stackSize;
}sqStack;

typedef double bElemType;
typedef struct
{
bElemType *base;
bElemType *top;
int stackSize;
}bsqStack;

void InitStack(sqStack *s)
{
s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if (!s->base) //如果分配失败退出程序
{
exit(0);
}
s->top = s->base;//栈的初始化时栈顶和栈底指向同一个地址
s->stackSize = STACK_INIT_SIZE;
}

void Push(sqStack *s, ElemType e)
{
//如果栈已经满了则再追加空间
if (s->top - s->base >= s->stackSize)
{
s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) *sizeof(ElemType));
if(!s->base) //如果分配失败退出程序
   exit(0);
}
*(s->top) = e;// 给当前的栈顶赋值
s->top++; // 然后栈顶元素加一
}

void Pop(sqStack *s, ElemType *e)
{
if (s->top == s->base)
{
return ;
}
*e = *--(s->top); // 出栈时栈顶先减一再取当前的栈顶的元素给e
}

// 有的时候用指针，有的时候用不用指针，一般对内容修改的用指针，其余的不用指针
int StackLen(sqStack s)
{
return (s.top - s.base);
}

void bInitStack(bsqStack *s)
{
s->base = (bElemType *)malloc(STACK_INIT_SIZE * sizeof(bElemType));
if (!s->base) //如果分配失败退出程序
{
exit(0);
}
s->top = s->base;//栈的初始化时栈顶和栈底指向同一个地址
s->stackSize = STACK_INIT_SIZE;
}

void bPush(bsqStack *s, bElemType e)
{
//如果栈已经满了则再追加空间
if (s->top - s->base >= s->stackSize)
{
s->base = (bElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) *sizeof(bElemType));
if(!s->base) //如果分配失败退出程序
   exit(0);
}
*(s->top) = e;
s->top++;
}

void bPop(bsqStack *s, bElemType *e)
{
if (s->top == s->base)
{
return ;
}
*e = *--(s->top);
}

// 有的时候用指针，有的时候用不用指针，一般对内容修改的用指针，其余的不用指针
int bStackLen(bsqStack s)
{
return (s.top - s.base);
}
/*
DestroyStack(sqStack *s)
{
int i ,len;
len = s->stackSize;printf("len = %d\n",len);
for (i=0; i<len ;i++)
{printf("333\n");
   free(s->base);printf("111\n");
   s->base++;printf("222\n");
}
s->base = s->top = NULL;
s->stackSize = 0;
}

DestroyBStack(bsqStack *s)
{
int i ,len;
len = s->stackSize;
for (i=0; i<len ;i++)
{
   free(s->base);
   s->base++;
}
s->base = s->top = NULL;
s->stackSize = 0;
}
*/
DestroyStack(sqStack *s)
{
free(s->base);
s->base = s->top = NULL;
s->stackSize = 0;
}

DestroyBStack(bsqStack *s)
{
free(s->base);
s->base = s->top = NULL;
s->stackSize = 0;
}

int zhong_revert_hou()
{
sqStack s;
char c,e;
InitStack(&s);

int li = 0;
printf("请输入中缀表达式，以 = 作为结束标志：\n");
scanf("%c",&c);
while (c != '=')
{
while (c >= '0' && c <= '9') // 处理连续数字
{
printf("%c",c);
string = c;
scanf("%c",&c);
if ((c < '0' || c > '9') && '.' != c) // 不是数字才打印空格，使得中缀表达式数字之间有该有的空格,因为数字可以是多位数的
{
printf(" ");
string = ' ';
}
if ('.' == c)
{
   printf("%c",c);
   string = c;
}
}
if ( ')' == c)          // 如果输入为右括号，则表明栈中必定会有左括号
{
Pop(&s,&e);          // 栈中元素和左括号比较则出栈，直到遇到左括号
while ('(' != e)    //比较栈顶元素是不是左括号
{
printf("%c ",e); // 出栈时打印数据
string = e;
string = ' ';
if (StackLen(s))
{
   Pop(&s,&e);
}
else
{
   break;
}
}
}
else if ( '+' == c || '-' == c)
{
if ( !StackLen(s))
{
Push(&s,c);// 如果栈为空，则将输入的符号入栈
}
else       // 不为空时，先出栈
{
do
{
Pop(&s,&e);// 通过pop得到当前栈顶元素的值
if ('(' == e)
{
Push(&s,e);// 如果左括号再重新压栈
}
else    // 可能为+ - * / 这几种可能
{
printf("%c ",e);//否则将栈内数据打印出来
string = e;
string = ' ';
}
}while(StackLen(s) && '(' != e);// 如果不为空并且不是左括号则继续出栈
Push(&s,c);
}
}
else if( '*' == c || '/' == c )
   {
         if(StackLen(s))
         {
            Pop(&s,&e);
            while('*' == e || '/' == e)//当栈顶元素为* / 时则弹栈顶元素
            {
               printf("%c ",e);
               string = e;
               string = ' ';
               if (StackLen(s))
               {
                     Pop(&s,&e);
               }
               else
               {
                     break;
               }
            }
            if ('(' == e || '+' == e || '-' == e) // 当pop后刚好为（，+ - 均需要压栈
            {
               Push(&s,e);
            }
         }
         Push(&s,c);
   }
   else if('('== c)
   {
         Push(&s,c);
   }
else if ('=' == c)
{
break;
}
else
{
printf("\n 出错，用户输入错误!\n");
}
scanf("%c",&c);
}
while ( StackLen(s))
{
Pop(&s,&e);
printf("%c ",e);
string = e;
   string = ' ';
}
printf("\n");
string= '\0';
printf("%s \n",string);
string= '=';
DestroyStack(&s);
return 0;
}

/*
测试用例：
1*2/3=
(((3.5*2-4.5+0.5)*8)+(9/5)*4)-5= 31.2
12*(6-3)+6/2*3= 45
(1-2)*(4+5)= -9
4.6-(-3/4+1.6-4-3/4)=暂时还不能处理带负号的数字
4.6-(3/4+1.6-4-3/4)= 7
*/

int main()
{
bsqStack s;
char c;
double d,e;
char str;
int i = 0;
zhong_revert_hou();
bInitStack(&s);
printf("请按逆波兰表达式输入待计算数据，数据与运算符之间用空格隔开，以 = 作为结束标志：\n");
char *p = string;
c = *p++;
//scanf("%c",&c);
while (c != '=')
{
while(isdigit(c) || c == '.')
{
str = c;
str = '\0';
if( i >= 10)
{
printf("error:输入的单个数据过大！\n");
return -1;
}
//scanf("%c",&c);
c = *p++;
if( c == ' ')
{
d = atof(str);
bPush(&s,d);
i = 0;
break;
}
}
switch(c)
{
case '+':
bPop(&s,&e);
bPop(&s,&d);
bPush(&s,d+e);
break;
case '-':
bPop(&s,&e);
bPop(&s,&d);
bPush(&s,d-e);
break;
case '*':
bPop(&s,&e);
bPop(&s,&d);
bPush(&s,d*e);
break;
case '/':
bPop(&s,&e);
bPop(&s,&d);
if ( e != 0)
{
bPush(&s,d/e);
}
else
{
printf("\nerror:除数不能为零！\n");
return -1;
}
break;
}
//scanf("%c",&c);
c = *p++;
}
bPop(&s,&d);
printf("\n 最终的计算结果为：%f\n",d);
DestroyBStack(&s);
return 0;
}

/* 将中缀表达式（即标准形式的表达式）转换为后缀式。
1.当读到一个操作数时，立即将它放到输出中。输出到终端。
2.如果读到的为左圆括号时，由于左圆括号的优先级最高，栈顶的任何元素都不可能被左圆括号从栈中置换出来，因此无须判断栈是否为空，直接压栈。
3.当读到一个操作符（其中操作符可能为+ - * /） ,如果此时栈为空，则直接推入栈中;如果栈不为空时，则先pop栈顶元素，比较读到的操作符和栈顶元素的优先级。
4.置换规则：当读入的操作符比 Pop出的栈顶元素的优先级低或相等时，则输出Pop出的操作符，继续循环，直到栈顶元素比读入的操作符运算级低或者遇到（，停止循环，将pop出的当前的操作符或（重新压栈，再将读入的操作符压栈
5.当读入）时，则Pop栈中元素，输出到终端，直到遇到（停止，（不需要打印到终端，（无需压栈
6.对4进行示例分析：当读入+ - 时，如果Pop的栈顶元素为（则重新压栈，如果是（或者栈为空，退出循环，否则Pop并输出所有操作符，因为+ - * / 的运算符都不比+ - 的运算符低
7.对读入的 * / 运算符，如果栈为空，直接压栈;否则Pop 栈顶元素，比较如果栈顶元素为 * 或 /时，循环pop并输出，当栈为空或栈顶元素不为 * 或 /时退出循环判断循环退出的原因，如果栈顶元素不为*或/时，即为( - + 时，重新压栈，再将当前读入的操作符压栈
*/

/*
目的：将中缀表达式（即标准形式的表达式）转换为后缀式。
例子：a+b*c+(d*e+f)*g转换成abc*+de*f+g*+

转换原则：
1.当读到一个操作数时，立即将它放到输出中。操作符则不立即输出，放入栈中。遇到左圆括号也推入栈中。
2.如果遇到一个右括号，那么就将栈元素弹出，将符号写出直到遇到一个对应的左括号。但是这个左括号只被弹出，并不输出。
3.在读到操作符时，如果此时栈顶操作符优先性大于或等于此操作符，弹出栈顶操作符直到发现优先级更低的元素位置。除了处理）的时候，否则决不从栈中移走"（"。操作符中，+-优先级最低，（）优先级最高。
4.如果读到输入的末尾，将栈元素弹出直到该栈变成空栈，将符号写到输出中。

解如下：
首先，读入a，并送到输出，然后+被读入并压入栈中。接下来b读入并送到输出，此时状态如下：
stack:                                     输出：a b
      +
backtop
接下来读入*，由于优先性比栈顶元素+大（原则3），因此被压入栈顶，接着读入c，并送到输出：
stack:                                  输出：a b c
   + *
back top
然后读入+，由于此时栈顶元素为*，优先级比+大，因此将*弹出，弹出后原来的+变成栈顶元素，由于+的优先性和当前读入的+优先性相等，因此也被弹出（原则3），最后将读入的+压入栈中。因此此时状态如下：
stack:                                     输出：a b c * +
         +
backtop
下一个读入的符号是（，由于具有最高优先级，因此将其放入栈中，然后读入d:
stack:                                     输出：a b c * + d
         + (
back top
继续读入，此时读入*，除非处理），否则（决不弹出（原则3），因此*被压入栈中，接下来读入e,并送到输出：
stack:                                  输出：a b c * + d e
         + ( *
back    top
再往后读入的符号是+，将*弹出并输出。（原则3，与之前步骤相似），然后将+压入栈中，接着读入f并送到输出：
stack:                            输出：a b c * + d e * f
      + ( +
back    top
现在读入），因此弹出栈元素直到遇到“（”（原则2）：
stack:                            输出： a b c * + d e * f +
         +
backtop
下面又读入一个*，被压入栈中，然后读入g并输出：
stack:                                  输出： a b c * + d e * f + g
      + *
back top
现在输入为空，弹出栈中所有元素：
stack :                                  输出： a b c * + d e * f + g * +
empty

自此全部完成。（总结自数据结构与算法导论C语言版）

*/

页: [1]

鱼C论坛's Archiver

中缀表达式计算器 源代码

中缀表达式计算器源代码