前缀表达式：符号在前，如-×+3456
中缀表达式：符号在中间，如(3 + 4) × 5 - 6
后缀表达式：符号在最后，如34+5×6-，后缀表达式不出现括号。
1.遇到数字:直接输出(添加到后缀表达式中)
2.栈为空时，遇到运算符，直接入栈
3.遇到左括号:将其入栈
4.遇到右括号:执行出栈操作，将栈的元素全部输出，直到弹出栈的是左括
号为止，且左括号不输出直接删除
5.遇到其他运算符:加减乘除:若当前运算符小于等于栈中运算符优先级，依次出栈，然后再将该运算符入栈
6.最终将栈中的符号依次出栈，输出。
运算符优先级(常用的记忆一下，和常识吻合)
1 [] () (同级)
3 */
4 +-
//定义一个运算符栈op
struct{
char data[MAXSIZE]; //存放运算符
int top; //栈顶指针
}op;
void trans(char exp[],char postexp[]){
char ch;
int i,j; //i是中缀exp的下标，j是后缀postexp的下标
op.top=-1;
ch=exp[i]; //获取输入的第一个字符
i++;
while(ch!='\0'){
switch(ch){
case '(': //遇到左括号直接入栈
op.top++;
op.data[op.top]=ch;
break;
case ')': //遇到右括号，栈顶元素不断出栈直到遇到左括号
while(op.data[op.top]!='('){
postexp[j]=op.data[op.top];
j++;
op.top--;
}
op.top--; //遇到了左括号，直接删除
break;
case '+': //因为加减运算符优先级最低，不大于任何其他运算符，所以直接入栈
case '-':
while(op.top!=-1&&op.data[op.top]!='('){ //栈不为空且没有遇到左括号，都直接出栈
postexp[j]=op.data[op.top];
j++;
op.top--;
}
op.top++; //即：栈为空或遇到了左括号，当前运算符进栈
op.data[op.top]=ch;
break;
case '*':
case '/':
while(op.top!=-1&&op.data[op.top]!='('&&(op.data[op.top]=='*'||op.data[op.top]=='/')){
postexp[j]=op.data[op.top]; //栈不为空且没有遇到左括号且遇到了同级符号：都出栈
j++;
op.top--;
}
op.top++; //不满足上述时，入栈
op.data[op.top]=ch;
break;
case ' ':break; //过滤空格
//default一般用在最后，表示非以上的任何情况下而发生的情况，
default:
while(ch>='0'&&ch<='9'){ //输入的是数字
postexp[j]=ch; //直接入栈
j++;
ch=exp[i]; //遍历下一个数字
i++;
}
i--;
postexp[j]='#'; //用#标识一个数值串结束
j++;
break;
}
ch=exp[i];
i++;
}
while(op.top!=-1){ //此时exp扫描完毕，栈不空时出栈并存放到postexp中
postexp[j]=op.data[op.top];
j++;
op.top--;
}
postexp[j]='\0'; //添加结束标识，后缀表达式输入完毕
}1) 先按照运算符的优先级对中缀表达式加括号，
先计算2*(1+6)，加上括号，得到5+(2*(1+6))-8/2
再计算除法，得到5+(2*(1+6))-(8/2)
再计算加法，得到(5+(2*(1+6)))-(8/2)
最后进行减法，得到((5+(2*(1+6)))-(8/2))
2) 将每一个右括号替换成其离得最近的符号
得到 ( ( 5 ( 2 ( 1 6 + * + (8 2 / -
3) 去除所有的左括号 ，得到 5 2 1 6 + * + 8 2 / -
该方法不能用程序实现
- 从右至左扫描表达式
- 遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈
- 重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
示例：
计算前缀表达式的值：- + 1 × + 2 3 4 5
可以看到，用计算机计算前缀表达式是非常容易的，不像计算后缀表达式需要使用正则匹配
与前缀表达式类似，只是顺序是从左至右：
- 从左至右扫描表达式
- 遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈
- 重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
示例：
计算后缀表达式的值：1 2 3 + 4 × + 5 -
1）从左至右扫描，将1，2，3压入栈；
2）遇到+运算符，3和2弹出，计算2+3的值，得到5，将5压入栈；
3）遇到4，将4压入栈
4）遇到×运算符，弹出4和5，计算5×4的值，得到20，将20压入栈；
5）遇到+运算符，弹出20和1，计算1+20的值，得到21，将21压入栈；
6）遇到5，将5压入栈；
7）遇到-运算符，弹出5和21，计算21-5的值，得到16为最终结果
struct{
float data[MAXSIZE];
int top; //栈顶指针
};
float compvalue(char postexp[]){
float d;
char ch;
int i=0; //i作为postexp下标
st.top=-1;
ch=postexp[i];
i++;
while(ch!='\0'){
switch(ch){
case '+':
st.data[st.top-1]=st.data[st.top-1]+st.data[st.top];
st.top--;
break;
case '-':
st.data[st.top-1]=st.data[st.top-1]-st.data[st.top];
st.top--;
break;
case '*':
st.data[st.top-1]=st.data[st.top-1]*st.data[st.top];
st.top--;
break;
case '/':
if(st.data[st.top]!=0){
st.data[st.top-1]=st.data[st.top-1]/st.data[st.top];
}else{
printf("除零错误！\n");
exit(0); //异常退出
}
st.top--;
break;
default:
d=0;
while(ch>='0'&&ch<='9'){
d=d*10+ch-'0'; //将数字字符转换成对应的数字存入d
ch=postexp[i];
i++;
}
st.top++;
st.data[st.top]=d;
}
ch=postexp[i];
i++;
}
return st.data[st.top];
}#define MAXSIZE 100
#include <stdio.h>
int main()
{
int i = 0;
char exp[] = {"(2*2)*1+3*2/1"};
char postexp[MAXSIZE];
trans(exp,postexp);
while (postexp[i] != '\0')
{
printf("%c",postexp[i]);
i++;
}
printf("\n");
printf("运算结果为:%f.\n", compvalue(postexp));
return 0;
}
操作数直入左栈
运算符入栈有规则
若遇栈空直接入栈
若栈不空看优先级
栈顶元素优先级只有大于等于扫描元素的优先级才出栈
否则遇到都入栈
左括号入栈直到遇到右括号吐出来
（1）准备两个空栈，数字入左栈，符号入右栈
（2）5进左栈，+进右栈
（3）7进左栈，*的优先级大于+，直接进右栈
（4）3进左栈
（5）*的优先级等于*，第一个*出栈，并且左栈要弹出两个元素进行运算，即3*7=21，并将新的运算结果压入左栈
（6）第二个*进右栈，左括号（直接进栈
（7）2进左栈
（8）+直接进右栈
（9）1进左栈
（10）遇到右括号，之前的元素全部弹出进行运算直到遇见左括号
（11）1+2=3，将3压入左栈，（左括号删除
（12）21*3=63，将63压入左栈
（13）63+5=68，最后的左栈元素为68
- 前缀表达式和后缀表达式计算的时候都是从一个方向扫描表达式，遇到数字压入栈，遇到运算符弹出栈顶的两个数进行运算并将结果入栈，重复知道结束
- 前缀和后缀表达式已经内在地包含运算顺序，因此不用括号来确定优先级