栈的应用
数制转换 【链栈】表达式转换（中缀转前缀，中缀转后缀）表达式求值（前缀式求值，后缀式求值）
// 数制转换
void Convertion(int n,in j)
{
// 将十进制的 n 转换为 j 进制
LinkStack s;
int x;
s.top = NULL;
do{
x = n % j;
n = n / j;
Push(s,x);
}while(n) // n == 0 循环结束
while(Pop(s,x)) court<<x<<endl;
}
表达式转换
中缀表达式，前缀表达式，后缀表达式
中缀表达式:(平常的数学式子) 运算符在两运算数的中间
前缀表达式（波兰表达式）：运算符号在两操作数的前面； 运算顺序：对前缀式 从右向左扫描
后缀表达式（逆波兰表达式）：将运算符放两操作数后； 运算顺序：对后缀式 从左到右（比较符合平时的运算习惯）
中缀表达式转换为后缀表达式或前缀表达式 目的：方便计算机运算
手动转换（中缀转前缀；中缀转后缀）
步骤：
step1: 加括号
step2:提运算符（前缀提前面；后缀提后面）
a+b +ab ab+
前缀表达式（波兰表达式）
在前缀表达式不存在运算符的优先级问题，计算顺序按照运算符出现的先后次序进行计算时会，从右向左扫描前缀式扫描到运算符就把栈顶两个操作数进行计算，结果进栈，直至表达式运算完
后缀表达式（逆波兰表达式）
计算顺序完全按照 运算符出现的先后次序进行从左向右扫描后缀式扫描到运算符就取栈顶两元素进行相应的运算，结果入栈，直至表达式算完
算法 中缀转后缀
从左向右 扫描中缀表达式
<a>扫描的是 操作数：直接输出
<b>扫描的是 运算符：入栈，左括号“（”也入栈
<1> if 扫描的是 右括号） ，则弹出pop直至遇到栈中的左括号（ 左括号只弹出不输出
<2> if 栈顶的运算符优先级 > 扫描的运算符的优先级，一直弹出，直至栈顶运算符的优先级 < 扫描运算符优先级，再将扫描运算符入栈
<c> if 输入结束，将栈中剩余运算符依次弹出
void Change(SqStack *s,Elemtype str[])
{
int i = 0;
Elemtype e;
InitStack(s);
while(str[i] != \0')
{
// 直接输出数字字符 扫描到运算符则 输出空格结束循环
while(isdigit(str[i]))
{
printf("%c",str[i++]);
if(!isdigit(str[i])) printf(" ");
}
// +号和-号优先级是最低的【‘（’优先级更低】
//根据 栈顶元素优先级 > 扫描元素优先级，则一直弹出直至栈顶元素优先级 小于扫描的优先级
//可知，栈空时+-入栈 或者 栈顶元素为 左括号（ 入栈
//其他情况则一直出栈，直至栈空或者遇到左括号（
//弹出完了 再将扫描的运算符 入栈
if(str[i] == '+' || str[i] == '-')
{
if(SEmpty(s)) push(s,str[i]);
else
{
do
{
pop(s,&e);
if(e == '(' ) push(s,e);
else printf("%c",e)
}while(!Sempty && e != '(');
push(s,str[i]);
}
}
//扫描的是右括号 则一直弹出 直至遇到左括号
//左括号只弹出 不输出
else if( str[i] == ')' )
{
pop(s,&e);
while(e != '(')
{
printf("%c",e);
pop(s,&e);
}
}
//*号/号优先级最高直接入栈；左括号直接入栈
else if(str[i] == '*' || str[i] == '/' || str[i] == '(' ) push(s,str[i]);
else if(str[i] == '\0') break;
else {printf("input is not valid"); return ;}
i++;
}
//最后表达式若扫描结束，则将栈内剩余的 运算符输出
while(!SEmpty)
{
pop(s,&e);
printf("%c",e);
}
}
算法-后缀表达式求值
<a>从左向右 扫描后缀表达式【扫描字符串-】
<b>
扫描的是操作数：则直接入栈
扫描的是运算符：则取栈顶两元素，进行相应计算，结果入栈
例子：pop(s,&e);b = e;pop(s,&e);a = e; a +-*/ b = c; push(s,c);
当取两操作数运算时，第一个栈顶元素为操作数，第二个栈顶元素为被操作数（关系类同与除数与被除数）
直至后缀表达式扫描完毕
