前缀、中缀与后缀表达式

计算机中一般使用三种表达式，分别是中缀表达式(Infix)、前缀表达式(Prefix)、后缀表达式(Postfix)。

下表列出了它们的基本表示形式：

类型 Infix Prefix Postfix
形式 <operand><operator><operand> <operator><operand><operand> <operand><operand><operator>
例子 a+b*c +a*bc abc*+

后缀表达式的计算方法

为什么要将表意清晰的中缀表达式转换成形式比较特殊的后缀表达式呢？这是因为中缀表达式的运算需要人为地遵循一些运算法则，而后缀表达式只需要遵循一个固定的运算法则即可完成运算。

后缀表达式的计算方法为：

从左到右对后缀表达式进行扫描，当遇到运算符时，将运算符与它前面两个数字组合成一个算式进行计算，用结果取代两个数字以及运算符的位置，继续向后扫描，直到表达式变成一个值，该值即为表达式的值。

我们发现，这与栈的工作模式非常类似，于是，可以写出以下代码：

int EvaluatePostfix(int exp[]){
    stack<int> S;
    for(int i = 0 ; i <= strlen(exp)-1 ; i++){
        if(exp[i] is operand)//如果是操作数，就入栈
            S.push(exp[i]);
        else if(exp[i] is operator){//如果是操作符，将栈最上面两个操作数pop并保存在op1和op2中
            int op1 = S.top();
          	S.pop();
            int op2 = S.top();
            S.pop();
            res = Perform(exp[i],op1,op2);//Perform函数读取操作符和两个操作数并运算，返回得数
            S.push(res);//将得数入栈
        }
    }
    return S.top();//最后留在栈中的数字即为表达式的得数
}

将中缀表达式转换为后缀表达式

那么如何将Infix转换为Postfix，从而可以被程序计算呢？

对比两种表达式

Infix: A + B * C

Postfix:A B C * +

我们发现操作数之间的相对位置并无改变，只是操作符的位置发生变化。下面提供一个转换的方法，依然使用栈来实现。

1.

Infix A + B * C - D * E
Postfix A
Stack

2.

Infix A + B * C - D * E
Postfix AB
Stack +
  1. 现在我们遇到了第二个符号，如果此时栈顶符号的运算级别大于等于该符号，那么就将栈顶的符号弹出并且加入Postfix，直到不符合该条件或者栈为空时，将该符号（也就是遍历到的符号）入栈。
Infix A + B * C - D * E
Postfix AB
Stack + *
  1. 直到遍历结束，将栈中剩余符号依次全部弹出并加入Postfix。
Infix A + B * C - D * E
Postfix A B C * + D E * -
Stack

但是我们并没有考虑Infix带括号的情况。如果表达式带括号的话，解决方案如下：

  1. 遇到左括号让左括号入栈，如果栈顶是左括号，遇到操作符直接入栈

  2. 直到遇到右括号，将栈顶的元素弹出并加入Postfix直到遇到对应的左括号时停止

综合以上方法可以写出对应代码

void InfixtoPostfix(char exp[],char res[]){
    stack<char> S;
    int j=0;
    for(int i=0;i<=strlen(exp)-1;i++){
        if(exp[i] is operand)
            res[j++] = exp[i];
        else if(exp[i] is operator){
          
            while(!S.empty()&&HasHigherPrec(S.top,exp[i])&&!IsOpeningParentheses(S.top())){//HasHigherPrec函数即栈顶符号优先级大于等于第i个符号时返回true，否则返回false
 //IsOpeningParentheses函数功能是检查栈顶是否是左括号，是返回true，否返回false
                res[j++] = S.top();
                S.pop();
            }
            S.push(exp[i]);
        }
        else if(exp[i] == '(')
            S.push(exp[i]);
        else if(exp[i] == ')'){
            while(!S.empty()&&!IsOpeningParentheses(S.top())){
                res[j++] = S.top();
                S.pop();
            }
            S.pop();//这次pop是为了pop出栈中的左括号
        }
    }
    while(!S.empty()){
        res[j++] = S.top();
        S.pop();
    }
}

编写10以内的混合运算计算器

任务

输入包括10以内的数字和+、-、*、(、)运算符的合法表达式，输出它的Infix、Postfix以及运算结果。

代码

#include<iostream>
#include<stack>
using namespace std;

bool Isoperator(char c){
	if(c == '+'||c == '-'||c == '*')
	return true;
	else
	return false;
}
bool HasHigherPrec(char a,char b){
	if(b == '+'||b == '-')
	return true;
	else{
		if(a == '*') return true;
		else return false;
	}
}
bool IsopeningPar(char c){
	if(c == '(') return true;
	else return false;
}
void InfixtoPostfix(char exp[],char res[]){
	int j=0;
	stack<char> S;
	for(int i = 0; i <= strlen(exp)-1 ;i++){
		if(exp[i]>=48&&exp[i]<=57){
			res[j++] = exp[i];
		}
		else if(Isoperator(exp[i])){
			while(!S.empty()&&HasHigherPrec(S.top(),exp[i])&&!IsopeningPar(S.top())){
				res[j++] = S.top();
				S.pop();
			}
			S.push(exp[i]);
		}
		else if(exp[i]=='(')
		S.push(exp[i]);
		else if(exp[i]==')'){
			while(!S.empty()&&!IsopeningPar(S.top())){
				res[j++] = S.top();
				S.pop();
			}
			S.pop();
		}
	}
	while(!S.empty()){
		res[j++] = S.top();
		S.pop();
	}
}
int Perform(char c,int a,int b){
	if(c == '+')
	return b+a;
	if(c == '-')
	return b-a;
	if(c == '*')
	return b*a;
}	

int EvaluatePostfix(char res[]){
	stack<int> A;
	int op1,op2,op;
	for(int i=0;i<=strlen(res)-1;i++){
		if(!Isoperator(res[i]))
			A.push((int)(res[i]-'0'));
		else if(Isoperator(res[i])){
			op1 = A.top();
			A.pop();
			op2 = A.top();
			A.pop();
			op = Perform(res[i],op1,op2);
			A.push(op);
		}
	}
return A.top();
}
int main(){
	char exp[100];
	char res[100];
	gets(exp);
	printf("Infix: %s\n",exp);
	InfixtoPostfix(exp,res);
	printf("Postfix: %s\n",res);
	printf("The result is %d",EvaluatePostfix(res));
	return 0;
}

输入/出结果

((1+2)*3-4)*5+(6-7)
Infix: ((1+2)*3-4)*5+(6-7)
Postfix: 12+3*4-5*67-+
The result is 24