#include <stdio.h>#include <string.h> /* strlen() */#include "SeqStack.h"/* 判断字符是否是数字 */int isDigit(char c){	return (('0' <= c) && (c <= '9'));}/* 进行四则运算 result = d1 op d2 */int doOperation(ElementType d1, char op, ElementType d2){	switch(op) {	case '+':		return d1 + d2;	case '-':		return d1 - d2;	case '*':		return d1 * d2;	case '/':		return d1 / d2;	}	return -1;}/* 计算后缀表达式 */int calSuffixExp(char *exp){	int i, result;	ElementType d1, d2;	SequenceStack dataStack; /* 运算数的栈 */	initSeqStack(&dataStack, strlen(exp));	for(i=0; exp[i]!='\0'; i++) {		if (isDigit(exp[i])) { /* 如果是数字，直接压栈 */			pushSeqStack(&dataStack, exp[i]-'0');		}		else{ /* 如果是运算符，弹栈2个数字进行运算 */			popSeqStack(&dataStack, &d2);			popSeqStack(&dataStack, &d1);			result = doOperation(d1, exp[i], d2); /* 进行四则运算 */			pushSeqStack(&dataStack, result); /* 把运算结果压栈 */		}	}	popSeqStack(&dataStack, &result); /* 弹栈得到最后的结果*/	destroySeqStack(&dataStack);	return result;}static int opPrecedenceTable[256] = {0};void initOpPrecedenceTable(){	opPrecedenceTable['('] = 1;	opPrecedenceTable['+'] = 10;	opPrecedenceTable['-'] = 10;	opPrecedenceTable['*'] = 20;	opPrecedenceTable['/'] = 20;}/**op1 > op2, return 正数op1 = op2, return 0op1 < op2, return 负数*/int cmpOpPrecedence(char op1, char op2){	return opPrecedenceTable[op1] - opPrecedenceTable[op2];}/* 把中缀表达式转为后缀表达式 */int transInfix2Suffix(char *infixExp, char *suffixExp){	int i, j=0;	ElementType topOp;	SequenceStack opStack; /* 运算符的栈，利用内置数据类型的自动转换，把运算符（字符）当做整型来存放 */	initOpPrecedenceTable(); /* 初始化运算符的优先级 */	initSeqStack(&opStack, strlen(infixExp));	for(i=0; infixExp[i]!='\0'; i++) {		if (isDigit(infixExp[i])) {/* 如果是数字，直接输出 */			suffixExp[j++] = infixExp[i];		}		else{ /* 运算符 */			if (infixExp[i] == '(') {/* (直接 */				pushSeqStack(&opStack, infixExp[i]); 			}			else if (infixExp[i] == ')') {/* 弹栈至( */				for(;;) {					popSeqStack(&opStack, &topOp); /* 弹栈*/					if (topOp == '(') {						break;					}					suffixExp[j++] = topOp;				}			}			else{/* 需要与栈顶元素不断比较优先级 */				for(;;) {					/* 查看栈顶运算符 */					if (peakSeqStack(&opStack, &topOp) < 0) { /* 栈空 */						pushSeqStack(&opStack, infixExp[i]); /* 运算符压栈 */						break;					}					if (cmpOpPrecedence(infixExp[i], topOp) > 0) { /* 当前运算符大于栈顶 ，压栈*/						pushSeqStack(&opStack, infixExp[i]); /* 运算符压栈 */						break;					}					popSeqStack(&opStack, &topOp); /* 弹栈输出*/					suffixExp[j++] = topOp;				}			}		}	}	/* 弹出剩余的运算符 */	while(popSeqStack(&opStack, &topOp) >= 0) {		suffixExp[j++] = topOp;	}	suffixExp[j] = '\0';  	destroySeqStack(&opStack);	return j; /* 返回后缀表达式的长度 */}int main(){	char infixExp[] = "9+(3-1)*3+8/2";	char suffixExp[100];/*	char suffixExp[] = "931-3*+82/+"; */	int result;	transInfix2Suffix(infixExp, suffixExp);	printf("%s => %s\n", infixExp, suffixExp);	result = calSuffixExp(suffixExp);	printf("%s = %d\n", infixExp, result);	return 0;}