中缀表达式计算

2018-01-25 10:57:57来源:网络收集作者:管理员人点击

分享
第七城市

[var1]#include
#include
#include
/************************************
总结规则:
从左到右遍历中缀表达式的每个数字和符号,
若是数字则直接输出,若是符号,则判断其与栈顶符号的优先级,
是右括号或者是优先级低于栈顶符号,则栈顶元素依次出栈,直到
遇到左括号或栈空,那个低优先级的符号入栈。
个人总结:
(* /优先级很高,直接push入栈
栈内没有元素,+ -直接push入栈,否则pop栈内所有元素直到 (或者栈空,+ -才入栈
)不push,pop栈内,直到(
(数字直接输出,pop出来的符号也输出)
*********************************************/
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 10
#define STACKINCREMENT 5
#define MAXBUFFERSIZE 15
#define OUTPUTBUFFSIZE 1024
typedef char ElemType;
typedef int STATUS;
typedef struct Stack {
ElemType * top;
ElemType *base;
int stackSize;
}stack;
STATUS initStack(stack * s)
{
s->base = (ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType));
s->top = s->base;
s->stackSize = STACK_INIT_SIZE;
return OK;
}
STATUS Push(stack *s, ElemType e)
{
if (s->top - s->base >= s->stackSize)
{
s->base = (ElemType*)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
if (!s->base)return ERROR;
s->top = s->base + s->stackSize;
s->stackSize = s->stackSize + STACKINCREMENT;
}
*(s->top) = e;
++s->top;
return OK;
}
STATUS Pop(stack *s, ElemType * e)
{
if (s->base == s->top)return ERROR;
--s->top;
*e = *(s->top);
return OK;
}
STATUS clearStack(stack *s)
{
s->top = s->base;
return OK;
}
STATUS destoryStack(stack *s)
{
//for (int i = 0; i < s->stackSize; i++)
//{
free(s->base);
//s->base++;
//}
//printf("%d", *(s->base));
s->base = 0;
s->top = 0;
s->stackSize = 0;
return OK;
}
int StackLen(stack *s)
{
return (s->top - s->base);//一定要加括号
}
////////////////////////////上面是字符串栈---下面是double栈////////////////////////
typedef struct cStack {
double * top;
double *base;
int stackSize;
}cstack;
STATUS initcStack(stack * s)
{
s->base = (double*)malloc(STACK_INIT_SIZE * sizeof(double));
s->top = s->base;
s->stackSize = STACK_INIT_SIZE;
return OK;
}
STATUS cPush(stack *s, double e)
{
if (s->top - s->base >= s->stackSize)
{
s->base = (double*)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(double));
if (!s->base)return ERROR;
s->top = s->base + s->stackSize;
s->stackSize = s->stackSize + STACKINCREMENT;
}
*(s->top) = e;
++s->top;
return OK;
}
STATUS cPop(stack *s, double * e)
{
if (s->base == s->top)return ERROR;
--s->top;
*e = *(s->top);
return OK;
}
STATUS clearcStack(stack *s)
{
s->top = s->base;
return OK;
}
STATUS destorycStack(stack *s)
{
//for (int i = 0; i < s->stackSize; i++)
//{
free(s->base);
//s->base++;
//}
//printf("%d", *(s->base));
s->base = 0;
s->top = 0;
s->stackSize = 0;
return OK;
}
int cStackLen(stack *s)
{
return (s->top - s->base);//一定要加括号
}
/////////////////////////////////////////////////////////////////////////////////////
//输出缓冲区
char output[OUTPUTBUFFSIZE];
//缓冲区指针
int point = 0;
int main(int argc, char * argv[])
{
stack s;
int count = 0;
char c, k;
initStack(&s);//初始化栈
printf("请输入要运算的表达式:'#'结束(中缀)/n");
scanf("%c", &c);
while (c != '#')
{
while (isdigit(c) || c == '.')
{
//printf("%c", c);
output[point] = c;
point++;
scanf("%c", &c);
if (!isdigit(c))
{
output[point] = ' ';
point++;
}
}
if ('#' == c)//判断第二个while循环里面的输入除了数字的情况
{
break;
}
else if ('(' == c || '*' == c || '/' == c)//优先级最高,直接push
{
Push(&s, c);
}
else if ('+' == c || '-' == c)
{
if (StackLen(&s) == 0)
{
Push(&s, c);
}
else
{
Pop(&s, &k);
if ('*' == k || '/' == k)
{
//printf("%c ", k);
output[point] = k;
point++;
output[point] = ' ';
point++;
while (StackLen(&s) != 0 && '(' != k)
{
Pop(&s, &k);
if ('(' != k)//printf("%c ", k);
{
output[point] = k;
point++;
output[point] = ' ';
point++;
}
}
if ('(' == k) Push(&s, k);
Push(&s, c);
}
else
{
Push(&s, k);
Push(&s, c);
}
}
}
else if (')' == c)
{
do
{
Pop(&s, &k);
if ('(' != k)//printf("%c ", k);
{
output[point] = k;
point++;
output[point] = ' ';
point++;
}
} while ('(' != k);
}
//else {
//printf("输入错误!");
//break;
//}
scanf("%c", &c);
}
count = StackLen(&s);
for (int i = 0; i < count; i++)
{
Pop(&s, &k);
output[point] = k;
point++;
output[point] = ' ';
point++;
}
//结尾
output[point] = '/0';
point++;
printf("/n转化后的逆波兰表达式%s:/n", output);
/**********************************************************************
*上面是中缀表达式转逆波兰表达式的算法 结果在 output字符数组里面 /0结尾
**************************************************************************/
cstack s2;
initcStack(&s2);
//clearStack(&s);
double a, b, d;
char str[MAXBUFFERSIZE];//字符缓冲区
int j = 0;//缓冲区指针
point = 0;
/***************************************************
*这里需要注意一个问题
* scanf("%c",&c) 一次读入一个字符
*如果一次输入一个字符串的话,读入一个字符后,其余字符全部放在字符缓冲区,
*留给下一次 scanf,
*(输入的 回车 /n也是有ASCII码的,最好用getchar()清空缓冲区)
**************************************************/
c = output[point];
point++;
while (c != '/0')
{
//数字和数字之间的空格处理
while (isdigit(c) || c == '.') //输入的是数字或者是小数点的情况(isdigit内部是根据查ASCII看字符是否是数字)
{
str[j++] = c;
if (j >= MAXBUFFERSIZE)
{
printf("您输入的单个数字太长/n");
return 1;
}
//scanf("%c", &c);//读取输入缓冲区字符
c = output[point];
point++;
if (c == ' ') //如果是空格,就表示一个数字输入完成了(实际是字符串,存在缓冲区)空格的ASCII码是32
{
str[j] = '/0';//结束符(用于atof内部)
d = atof(str);//字符串转double(缓冲区内的所有字符,就是一个数字)
cPush(&s2, d);
j = 0;//恢复缓冲区指针,用于下一次使用
break;//退出循环这一层循环
}
}
switch (c)
{
case '+':
cPop(&s2, &a);
cPop(&s2, &b);
//d = a + b;
cPush(&s2, a+b);
break;
case '-':
cPop(&s2, &a);
cPop(&s2, &b);
cPush(&s2, b - a);
break;
case '*':
cPop(&s2, &a);
cPop(&s2, &b);
cPush(&s2, a*b);
break;
case '/':
cPop(&s2, &a);
cPop(&s2, &b);
cPush(&s2, b / a);
break;
}
c = output[point];
point++;
}
//getchar();//getchar 可以用来清空缓冲区
cPop(&s2, &d);
printf("/n运算结果是%f/n", d);
printf("/n%d/n", cStackLen(&s2));
//destoryStack(&s);
system("pause");
return 0;
}
第七城市

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台