学步园

一、问题描述

将用户输入的前缀表达式转化为后缀表达式后，就可以计算表达式的值。本文给出后缀表达式求值的具体实现。

例：有前缀表达式：8-(3+2*6)/5+4；转化为后缀表达式后为：8 3 2 6 * + 5 / - 4 +

二、算法实现

1.后缀表达式存储在一维数组中，遍历数组；

2.遍历过程中，当遇到的是数字时，则直接将其push到栈中；

3.当遇到的是标点符号时，则依次从栈中弹出两个数字，计算组成的表达式的值，并将结果入栈；

4.遍历结束后，栈中会有一个值，就是最终结果，将其弹出即可。

三、代码

#include <stdio.h>
#include <stdlib.h>
#include "stack_yutao.h"

void display_array(int array[]);
int postfix_caculation(int postfix_array[]);
elemtype caculate_value(elemtype a, elemtype array_i,elemtype b);
void convert_to_int(char postfix_array[], int postfix_int[]);

int main()
{
	int ans = 0;
	char postfix_array[] = "8326*+5/-4+";
	int postfix_int[15];//how to define the size ???
	convert_to_int(postfix_array,postfix_int);
//	display_array(postfix_int);
	ans = postfix_caculation(postfix_int);
	printf("This postfix array's value is %d !\n",ans);

	system("pause");
	return 0;
}

//计算后缀表达式的值
int postfix_caculation(int postfix_int[])
{
	elemtype result = 0;
	int i = 0;
	elemtype num1, num2, temp;
	int stack_size = 10; //定义栈的大小为10
	stack char_stack;         //声明栈
	stack *s = &char_stack;

	initStack(s,stack_size); //初始化栈

	while(postfix_int[i] != '\0') //遍历后缀表达式
	{
		if(0 <= postfix_int[i] && postfix_int[i] <= 9)
		{	
			push(s,postfix_int[i]);
		}else
		{
			get_top(s,&num1);
			pop(s);
			get_top(s,&num2);
			pop(s);
			temp = caculate_value(num2,postfix_int[i],num1);
			push(s,temp);
		}
		i ++;
	}
	get_top(s,&result);
	return result;
}

elemtype caculate_value(elemtype a, char array_i,elemtype b)
{
	elemtype result;
	switch(array_i)
	{
	case '+':
		result = a + b;
		break;
	case '-':
		result = a - b;
		break;
	case '*':
		result = a * b;
		break;
	case '/':
		result = a / b;
		break;
	default:
		printf("wrong postfix_array !\n");
		break;
	}
	return result;
}
void convert_to_int(char postfix_array[], int postfix_int[])
{
	int i = 0;
	while(postfix_array[i] != '\0')
	{
		if('0' <= postfix_array[i] && postfix_array[i] <= '9')
		{
			postfix_int[i] = postfix_array[i] - '0';
		}else
		{
			postfix_int[i] = postfix_array[i];
		}
		i ++;
	}
	postfix_int[i] = '\0';
}

//输出数组中的内容
void display_array(int array[])  
{  
	int i = 0;
    while(array[i] != '\0')
	{
		printf("%d ",array[i++]);
	}
    printf("\n");  
}