-
(1-2)*(4+5)
-
人类早就熟悉这种中缀表达式的计算方式，因为括号里边的要先进行计算。
-
但是计算机不喜欢了，因为我们有小括号中括号大括号，还允许一个嵌套一个，这样子计算机就要进行很多次if判断才行决定哪里先计算。
-
后来，在20世纪三十年代，波兰逻辑学家Jan.Lukasiewicz不知道是像牛顿一样被苹果砸到脑袋而想到万有引力原理，或者还是像阿基米德泡在浴缸里突发奇想给皇冠是否纯金做验证，总之他也是灵感闪现了，然后发明了一种不需要括号的后缀表达式，我们通常把它称为逆波兰表达式(RPN) 。
-
数字1和2进栈，遇到减号运算符则弹出两个元素进行运算并把结果入栈。
-
4和5入栈，遇到加号运算符，4和5弹出栈，相加后将结果9入栈。
-
然后又遇到乘法运算符，将9和-1弹出栈进行乘法计算，此时栈空并无数据压栈，-9为最终运算结果！
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
#define MAXBUFFER 10
typedef double ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stackSize;
}sqStack;
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;
}
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 = s->base + s->stackSize;
s->stackSize = s->stackSize + STACKINCREMENT;
}
*(s->top) = e; // 存放数据
s->top++;
}
Pop(sqStack *s, ElemType *e)
{
if( s->top == s->base )
return;
*e = *--(s->top); // 将栈顶元素弹出并修改栈顶指针
}
int StackLen(sqStack s)
{
return (s.top - s.base);
}
int main()
{
sqStack s;
char c;
double d, e;
char str[MAXBUFFER];
int i = 0;
InitStack( &s );
printf("请按逆波兰表达式输入待计算数据，数据与运算符之间用空格隔开，以#作为结束标志: \n");
scanf("%c", &c);
while( c != '#' )
{
while( isdigit(c) || c=='.' ) // 用于过滤数字
{
str[i++] = c;
str[i] = '\0';
if( i >= 10 )
{
printf("出错：输入的单个数据过大！\n");
return -1;
}
scanf("%c", &c);
if( c == ' ' )
{
d = atof(str);
Push(&s, d);
i = 0;
break;
}
}
switch( c )
{
case '+':
Pop(&s, &e);
Pop(&s, &d);
Push(&s, d+e);
break;
case '-':
Pop(&s, &e);
Pop(&s, &d);
Push(&s, d-e);
break;
case '*':
Pop(&s, &e);
Pop(&s, &d);
Push(&s, d*e);
break;
case '/':
Pop(&s, &e);
Pop(&s, &d);
if( e != 0 )
{
Push(&s, d/e);
}
else
{
printf("\n出错：除数为零！\n");
return -1;
}
break;
}
scanf("%c", &c);
}
Pop(&s, &d);
printf("\n最终的计算结果为：%f\n", d);
return 0;
}
// 5 - (6 + 7) * 8 + 9 / 4
// 5 - 13 * 8 + 9 / 4
// 5 - 104 + 2.25
// -99 + 2.25
// 5 6 7 + 8 * - 9 4 / +
- 那么如何将“(1-2)*(4+5)”转化为“1 2 – 4 5 + *”呢？
- 其实很简单，利用栈的“记忆”吧，符号都推入栈即可。
首先遇到第一个输入是数字1，数字在后缀表达式中都是直接输出，接着是符号“+”，入栈：
第三个字符是“(”，依然是符号，入栈，接着是数字2，输出，然后是符号“-”，入栈：
接下来是数字3，输出，紧跟着是“)”，此时，我们需要去匹配栈里的“(”，然后再匹配前将栈顶数据依次出栈（这就好比括号里优先执行的道理）：
紧接着是符号“”，直接入栈：
遇到数字4，输出，之后是符号“+”，此时栈顶元素是符号“”，按照先乘除后加减原理，此时栈顶的乘号优先级比即将入栈的加好要大，所以出栈。
栈中第二个元素是加好，按理来说大家平起平坐，但是按照先到先来后到的原则，栈里的加好呆得太久了，也要出栈。（同理如果栈里还有其他操作符，也是出栈）
最后把刚刚的那个加好入栈，操作如下图:
紧接着数字10，输出，最后是符号“/”，进栈：
最后一个数字5，输出，所有的输入处理完毕，但是栈中仍然有数据，所以将栈中符号依次出栈。
总结规则：从左到右遍历中缀表达式的每个数字和符号，若是数字则直接输出，若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号，则栈顶元素依次出栈并输出，直到遇到左括号或栈空才将的那个符号入栈。
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
typedef char ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stackSize;
}sqStack;
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;
}
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 = s->base + s->stackSize;
s->stackSize = s->stackSize + STACKINCREMENT;
}
*(s->top) = e; // 存放数据
s->top++;
}
Pop(sqStack *s, ElemType *e)
{
if( s->top == s->base )
return;
*e = *--(s->top); // 将栈顶元素弹出并修改栈顶指针
}
int StackLen(sqStack s)
{
return (s.top - s.base);
}
int main()
{
sqStack s;
char c, e;
InitStack( &s );
printf("请输入中缀表达式，以#作为结束标志：");
scanf("%c", &c);
while( c != '#' )
{
while( c>='0' && c<='9' )
{
printf("%c", c);
scanf("%c", &c);
if( c<'0' || c>'9' )
{
printf(" ");
}
}
if( ')' == c )
{
Pop(&s, &e);
while( '(' != e )
{
printf("%c ", e);
Pop(&s, &e);
}
}
else if( '+'==c || '-'==c )
{
if( !StackLen(s) )
{
Push(&s, c);
}
else
{
do
{
Pop(&s, &e);
if( '(' == e )
{
Push(&s, e);
}
else
{
printf("%c ", e);
}
}while( StackLen(s) && '('!=e );
Push(&s, c);
}
}
else if( '*'==c || '/'==c || '('==c )
{
Push(&s, c);
}
else if( '#'== c )
{
break;
}
else
{
printf("\n出错：输入格式错误！\n");
return -1;
}
scanf("%c", &c);
}
while( StackLen(s) )
{
Pop(&s, &e);
printf("%c ", e);
}
return 0;
}
网友评论