C/C++ 四則運算 VS Stack [PreFix（前序式）/ InFix（中序式）/ PostFix（後序式）]

資料來源: http://www2.lssh.tp.edu.tw/~hlf/class-1/lang-c/stack2.htm

GITHUB: https://github.com/jash-git/cpp_postfix

Code

#include <iostream>
#include <cstdio>       /* printf, fopen */
#include <cstdlib>     /* exit, EXIT_FAILURE */
using namespace std;

#define N 50
#define OP 5

char op[OP] = {'(','+','-','*','/'};
int op_priority[OP] = {0,1,1,2,2};//與op[OP]對應,用以存放運算子的優先順序

int priority(char c);
void to_postfix(char infix[], char postfix[]);


char stack[N]; // This is a global variable.
int top=-1;
// -------------------------
//  將資料 item 放入堆疊
// -------------------------

void push(char item){
	if (top>=N-1){
		printf("Stack full!\n");
		exit(-1);
	}
	stack[++top]=item;
}
// ------------------------------------
// 傳回堆疊頂端的資料，但並非取出
// ------------------------------------
int pop(){
	if (top==-1){
		printf("Stack empty!\n");
		exit(-1);
	}
	return stack[top--];
}

void stackPrint(){
	int i;
	printf("stack =");
	for (i=0; i<=top; i++)
		printf(" %c", stack[i]);
	printf("\n");
}

// ----------------------
// 判斷是否為空堆疊
// ----------------------
bool IsEmpty(void)
{
	return (top < 0) ? true : false;
}

// ----------------------
//  判斷堆疊是否滿溢
// ----------------------
bool IsFull()
{
	return (top >= N - 1) ? true : false;
}

// --------------------------
// 傳回堆疊頂端的資料
// --------------------------
char top_data()
{
	return stack[top];
}

// ---------------------------
// 傳回運算子 c 的優先序
// ---------------------------
int priority(char c)
{
	int i;

	for( i=0; i < OP; i++)
	if(op[i] == c)
	return op_priority[i];
	return -1;
}

// ------------------------------------
// 將中置式infix轉成後置式postfix
// ------------------------------------
void to_postfix(char infix[], char postfix[])
{
	int i=0, j=-1;
	char x, y;

	while((x=infix[i++]) != '\0'){
		switch(x){
			case '(' : push(x);
					   break;
			case ')' : while(! IsEmpty() && (x=pop()) != '(')
						postfix[++j]=x;
						break;
			case '+' :
			case '-' :
			case '*' :
			case '/' : y=top_data();
					while(priority(y) >= priority(x)){
							postfix[++j]=pop();
							y=top_data();
					}
					push(x);
					break;
			default : // x ?綅呾啋
					postfix[++j]=x;
		}
	}
	while(! IsEmpty())
		postfix[++j]=pop();
	postfix[++j]='\0';
}
bool IsDight(char c)
{
	return c>='0' && c<='9';
}
int calculate(char postfix[])
{
	int point=0;
	while(postfix[point]!='\0')
	{
		while(IsDight(postfix[point]))
			push(postfix[point++]);
	int a=pop()-'0', b=pop()-'0',c=0;
	switch(postfix[point])
	{
		case'+':c=b+a;
				break;
		case'-':c=b-a;
				break;
		case'*':c=b*a;
				break;
		case'/':c=b/a;
				break;
	}
	push(c+'0');
	point++;
	}
	return pop()-'0';
}
void pause()
{
    printf("Press Enter key to continue…");
    fgetc(stdin);
}
int main()
{
    setlocale(LC_ALL,"Chinese_Taiwan.950");
    //cout << "Hello world!" << endl;
	char infix[50], postfix[50];

	printf("請輸入運算式: ") ;
	scanf("%s",infix);
	to_postfix(infix,postfix);
	printf("\n\n中序式 : %s \t後序式 : %s\n",infix , postfix);
	printf("答案： %d\n", calculate(postfix));
	pause();
    return 0;
}

完整教學文: