逆波兰表达式

逆波兰表达式(Reverse Polish Notation)又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法，按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。

表达式

逆波兰表达式，它的语法规定，表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。例子：

正常的表达式逆波兰表达式
a+b —> a,b,+
a+(b-c) —> a,b,c,-,+
a+(b-c)d —> a,b,c,-,d,,+
a+d(b-c)—>a,d,b,c,-,,+
a=1+3 —> a,1,3,+,=

计算

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果.

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("%lf",d);

完整代码

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

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 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++;
}

ClearStack(sqStack *s)	//清空栈
{
    s->top = s->base;
}

DestroyStack(sqStack *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;
}

int StackLen(sqStack s)		//返回栈长度
{
    return(s.top - s.base );
}

pop(sqStack *s,ElemType *e)		//出栈
{
    if(s->top == s->base )
        return 0;
    *e = *--(s->top);
}

int main()
{
	sqStack s;
	char c;
	double d,e;
	char str[10];
	int i =0;
	InitStack(&s);

	printf("请输入表达式  以#结束：");
	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("%lf",d);

	return 0;
}