Stack OPND; //存储后缀【表达式】的栈
Stack OPTR; //存储【符号】的栈
OPTR.push('#') //将一个#压在最下面，做标识，为了更好统一比较

扫描原表达式，得到c
	if c==数字:
		放入OPND
	if c==符号：
		c前面的一个符号top（OPTR的栈顶元素）
		//c与top进行优先级比较
		if c<top：
			OPTR.pop()
			OPTR.push(top) //将c放入符号栈
		else if c>top：
			OPTR.push(c)  //将c放到符号栈
		else if c==top:
			continue

// 顺序栈
// 顺序栈
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define SElemType int
#include"2 SqStack.h"

void visit(SElemType e) { 
   
	printf("%d ",e);
}
void visit_optr(SElemType e) { 
   
	printf("%c ",e);
}
void Show(SqStack *pOPTR, SqStack *pOPND,char c) { 
   
	//printf("| 步骤 | 操作数栈OPND | 操作符栈OPTR | 输入字符 |\n");
	static int first = 1;
	if (first==1) { 
   
		printf("当前扫描的字符\t数字栈\t符号栈\n");
		first++;
	}
	printf("%c\t",c);
	StackTraverse(*pOPND, &visit);printf(" \t");
	StackTraverse(*pOPTR, &visit_optr);
	printf("\n");
}
//将操作符转换成矩阵下标
int getIndex(char c) { 
    
	switch(c) { 
   
	case '+': return 0;
	case '-': return 1;
	case '*': return 2;
	case '/': return 3;
	case '(': return 4;
	case ')': return 5;
	case '^': return 6;
	case '#': return 7;
	}
	return -1;
}
// 两个操作数比较
// c1>c2 TRUE
// c1<c2 FALSE
int compare_op(char c1,char c2) { 
   
	char result;
	static char priorityMatrix[8][8] = 
	{ 
     // + - * / ( ) ^ #
		{ 
   '<','<','<','<','>','<','<','>'}, //+
		{ 
   '<','<','<','<','>','<','<','>'}, //-
		{ 
   '>','>','<','<','>','<','<','>'}, //*
		{ 
   '>','>','<','<','>','<','<','>'}, ///
		{ 
   '>','>','>','>','>','>','>','>'}, //(
		{ 
   '<','<','<','<','=','<','<','>'}, //)
		{ 
   '>','>','>','>','>','<','>','>'}, //^
		{ 
   '<','<','<','<','<','<','<','='}  //#
	};
	// 转换下标
	int c1_index = getIndex(c1);
	int c2_index = getIndex(c2);
	// 矩阵
	result =  priorityMatrix[c1_index][c2_index];
	switch (result) { 
   
	case '<' : return -1; // c1<c2
	case '>' : return 1; // c1>c2
	case '=' : return 0; // c1=c2错误情况
	}
	return 0;
}
int Operate(int S1,char OP,int S2) { 
   
	switch (OP) { 
   
	case '+':
		return S1+S2;
	case '-':
		return S1-S2;
	case '*':
		return S1*S2;
	case '/':
		return S1/S2;
	
	case '^':
		return (int)pow(S1,S2);
	}
	return 0;
}

//表达式求值：规定为整数，未检查异常
/* 测试数据:
10+11+12#
10*(1*(2+6/3)-1)+3^(3-1)+1+1-2#
 */
int main() { 
   
	SqStack OPTR; //存放符号（操作符）
	SqStack OPND; //存放数值（操作数）
	char c; //每次获得的字符
	int num,S1,S2,result,tmp,OP; //存放数字
	//初始化
	InitStack(&OPTR);
	Push(&OPTR, '#');
	InitStack(&OPND);

	printf("请输入表达式：\n");
	c=getchar();
	num=0;
	while ( !StackEmpty(OPTR) ) { 
   
		if (c>='0' && c<='9') { 
    //数字
			num = num*10 + c-'0'; //保存数字

			Show(&OPTR, &OPND, c); //UI
			printf("\t\t\t\t【操作】是数字%d\n",num); //UI
		} else { 
    //操作符
			if (num!=0) { 
    //之前有数字
				Push(&OPND, num); //入栈
				printf("\t\t\t\t【操作】至此，前面的扫描中得到一个数字%d，入栈\n",num); //UI
				Show(&OPTR, &OPND, c); //UI
				num =0; //归为0
			}
			GetTop(OPTR, &OP); //取出操作符栈顶元素
			//与上一个符号比较优先级
			tmp = compare_op((char)c, (char)OP);
			printf("\t\t\t\t【操作】优先级比较：%c与%c\n",c,OP);
			if ( tmp==1 ) { 
    //c>tmp
				Push(&OPTR, c); //压栈

				Show(&OPTR, &OPND, c); //UI
				printf("\t\t\t\t【操作】将符号%c压栈\n",c); //UI
			} else if ( tmp==-1 ){ 
    //c<tmp
				Pop(&OPTR, &OP);
				Pop(&OPND, &S2); //先取出的是后面一位的数字 
				Pop(&OPND, &S1);
				result = Operate(S1, (char)OP, S2);
				Push(&OPND, result);

				Show(&OPTR, &OPND, c); //UI
				printf("\t\t\t\t【操作】进行计算%d%c%d=%d，将结果压栈\n",S1,OP,S2,result);//UI
			
				continue; //不执行c=getchar()，当前的c还没有处理完
			} else if (tmp==0){ 
   
				// 1. c=) OP=(
				// 2. c=# OP=#
				Pop(&OPTR,&tmp); //将栈顶删除

				Show(&OPTR, &OPND, c); //UI
				printf("\t\t\t\t【操作】当前操作符和栈顶操作符相同，删除栈顶操作符\n");
			}
			
		}
		c = getchar();
	}
	GetTop(OPND,&result);
	printf("\n计算结果：%d\n", result);
	return 0;
}