C++ 使用栈求解中缀、后缀表达式的值

乎语百科 331 0

1. 前言

表达式求值对于有知识积累的你而言，可以通过认知，按运算符的优先级进行先后运算。

但对计算机而言，表达式仅是一串普通的信息而已，需要通过编码的方式告诉计算机运算法则，这个过程中栈起到了至关重要的作用。

表达式由 2 部分组成：

  • 操作数。
  • 运算符。

在一个复杂的表达式中，操作数和运算符可以有多个，运算符之间存在优先级，且不同运算符所需要的操作数的数量也有差异。这时，表达式的计算过程就变得较复杂。为了简化问题，本文只限于讨论基于常量操作数和双目运算符的表达式。

在计算机中，表达式的描述可以有以下 3 种：

  • 后缀表达式：操作数，操作数，运算符。
  • 中缀表达式：操作数，运算符，操作数。数学上最常见的描述方式。
  • 前缀表达式：运算符，操作数，操作数。

本文将讨论后缀表达式和中缀表达式的计算过程。

2. 中缀表达式

平常所见最多的表达式是中缀表达式，如下所示：

4*6^(3+3*3-2*3)-8

对中缀表达式求值时需要创建 2 个栈。

  • 一个用来存储运算符的栈 optStack。
  • 一个用来存储操作数的栈numStack。
stack<int> numStack;
stack<char> optStack;

2.1 求值流程

扫描整个表达式，对不同类型（操作数和运算符）的字符采用不同的处理方案。

  • 遇到操作数时的处理方案

直接将其压入numStack中，如上述表达式中的第一个字符是 4，压入numStack栈中。

  • 扫描到运算符时的处理方案

如果运算符比optStack栈顶运算符的优先级高，则入栈。如果比optStack栈顶的运算符的优先级低，则弹出运算符，再从numStack栈中弹出 2 个操作数，对其进行运算，且把运算结果压入到numStack栈中。

这里就有一个问题，如何判断运算符的优先级？

基于数学常识，在常规的加减乘除四则运算表达式中：

  • 其运算符的优先级为:() > ^ > *、/、% > +、-`。
  • 有括号时，先算括号内的，后算括号外的，对于多层括号，由内向外进行。
  • 乘方连续出现时先算最右边的。

但是，这里需要知道， 因为使用到了出栈、入栈操作，运算符在栈外和栈内的优先级是不一样的。

如左括号(运算符，在栈外优先级是最高的，进栈后优先级则变得最低。这个很好理解，括号的本质是界限符号（ 界限了一个子表达式的范围，它并不具有运算能力），为了保证左括号后面的表达式中的运算符能正常入栈，就必须降低优先级别。当左括号遇到右括号时，表示由这一对括号所标识的子表达式运算结束。

Tips： 栈内、栈外优先级相同的运算符，栈内优先。

  • 一直反复上述过程，直到表达式扫描结束。

2.2 演示表达式4*6^(3+3*3-2*3)-8 的求值过程

  • 当一直扫描到第一个减号（-）时，两个栈都是在进行入栈操作。

  • 因 -(减法)运算符优先级低于optStack栈顶的*运算符。这时从optStack栈中弹出*，再从numStack中弹出3和3 两个操作数，进行乘法运算3*3=9，并把结果压入numStack栈中。

  • 计算完成后，因-（减法）和+（加法）的优先级相同，栈内优先。此时，把+从optStack栈中弹出，并从numStack中相继弹出9和3，计算3+9=12，并把结果压入numStack栈中。

  • 因-(减法)优先级大于栈中(的优先级，-入栈。

  • 继续扫描，直到遇到右括号。

  • 因右括号的优先级最低，或者说表示子表达式到此结束，此时从optStack栈中依次弹出运算符，从numStack中相应弹出 2 个操作数，计算后把结果压入numStack中，直到在optStack栈中遇到左括号。

弹出*对3和2进行计算。并把结果6压入numStack中。

弹出-运算符，并对numStack栈中的12和6进行计算。

  • (出栈，表示由括号表示的子表达式计算结束。继续扫描到第二个-

  • 因-优先级小于^，先做6^6=46656乘方运算 。

  • -优先级小于*，继续做乘法运算，46656*4=186624。

  • -入栈，最后一个数字 8入栈。

  • 因整个表达式结束，弹出-，做最后的减法运算186624-8=186616。整个表达式结束，numStack栈顶的结果为表达式的最后结果。

2.3 编码实现

中缀表达式求值的完整代码，仅针对只包括加、减、乘、除、括号常规运算符的表达式。

#include <iostream>
#include <stack>
#include <map>
#include <cmath>
#include <cstring>
using namespace std;
//运算符对象
struct Opt {
	//运算符名字
	char name;
	//栈内级别
	int stackInJb;
	//栈外级别
	int stackOutJb;
    //构造
	Opt(char name,int in,int out) {
		this->name=name;
		this->stackInJb=in;
		this->stackOutJb=out;
	}
	/*
	*栈外运算符和栈内运算比较
	*/
	bool compare(Opt* opt) {
		return this->stackOutJb > opt->stackInJb;
	}
	//显示
	void desc() {
		cout<<this->name<<"-"<<this->stackInJb<<"-"<<this->stackOutJb<<endl;
	}
};

//关联容器
map<char,Opt*> maps;
//初始化关联容器，本文限定表达式中只包括如下几种运算符
void mapOpt() {
	maps['^']=new Opt('^',3,4);
	maps['*']=new Opt('*',2,2);
	maps['+']=new Opt('+',1,1);
	maps['-']=new Opt('-',1,1);
	maps['(']=new Opt('(',0,4);
	maps[')']=new Opt(')',-1,-1);
}

int main(int argc, char** argv) {
	mapOpt();
    //操作数栈
	stack<int> numStack;
    //运算符栈
	stack<char> optStack;
    //以字符描述的表达式，最外层的括号用来标志表达式的开始和结束
	char exps[20]="(4*6^(3+3*3-2*3)-8)";
    //初始压入 (
	optStack.push(exps[0]);
	//栈内运算符
	Opt* opt;
	//栈外运算符
	Opt* opt_;
	for(int i=1; exps[i]!='\0' ; ) {
		if( !(exps[i]>='0' && exps[i]<='9')  ) {
			//栈内最初是 ) 运算符
			opt=maps[optStack.top()];
			//栈外运算符
			opt_=maps[exps[i]];
			//如果左右括号相遇
			if(opt_->name==')' && opt->name=='(') {
				//子表达式结束
				optStack.pop();
				i++;
				continue;
			}
			//比较
			bool com=opt_->compare(opt);
			if (com) {
				//入栈
				optStack.push(opt_->name);
				i++;
			} else  {
				//运算
				char n=opt->name;
				optStack.pop();
				int res;
				int optNum1=numStack.top();
				numStack.pop();
				int optNum2=numStack.top();
				numStack.pop();
				if(n=='*') {
					res=optNum2*optNum1;
				} else if(n=='+') {
					res=optNum2+optNum1;
				} else if(n=='-') {
					res=optNum2-optNum1;
				} else if(n=='^') {
					res= pow(optNum2,optNum1);
				}
				numStack.push(res);
			}
		} else {
			//数字字符
			numStack.push( exps[i]-'0' );
			i++;
		}
	}
	cout<<numStack.top()<<endl;
	return 0;
}

输出结果：

186616

3.后缀表达式

后缀表达式也称为逆波兰式，其求解过程比中缀表达式要简单，整个过程只需要一个操作数栈。所以往往会把中缀表达式转换成后缀表达式后再求解。

后缀表达式的求解流程：

  • 创建一个栈。
  • 把后缀表达式当成一个字符串，对字符串进行逐字符扫描。
  • 遇到操作数入栈，遇到运算符则从栈中取出 2 个操作数，运算后把结果压入栈。
  • 重复上述过程，直到扫描结束。则栈中的值为最终结果。

如下是求解后缀表达式8571-*+82/-的代码。

Tips：此后缀表达式对应的中缀表达式是： 8+5*(7-1)-8/2

#include <iostream>
#include <stack>
using namespace std;
int main() {
	char exp[20]="8571-*+82/-";
	stack<int> expStack;
	int num1;
	int num2;
	char opt;
	int res;
	for(int i=0; exp[i]!='\0'; i++) {
		if (exp[i]>='0' && exp[i]<='9') {
			//入栈
			expStack.push(exp[i]-'0');
		} else {
			//出栈
			num1=expStack.top();
			expStack.pop();
			//出栈
			num2=expStack.top();
			expStack.pop();
			//运算符
			opt=exp[i];
			switch(opt) {
				case '+':
					res=num2+num1;
					break;
				case '-':
					res=num2-num1;
					break;
				case '*':
					res=num2*num1;
					break;
				case '/':
					res=num2/num1;
					break;
			}
			expStack.push(res);
		}
	}
	cout<<expStack.top()<<endl;
	return 0;
}

执行后的输出结果：

34

4. 中缀转后缀表达式

虽然后缀表达式的计算过程要比中缀表达式简单很多，前提条件是要先把中缀表达式转换成后缀表达式。

转换流程：

  • 初始化一个运算符栈。
  • 自左向右扫描中缀表达式，当扫描到操作数时直接连接到后缀表达式上。
  • 当扫描到操作符时，和运算符栈栈顶的操作符进行比较。如果比栈顶运算符高，则入栈。如果比栈顶运算符低，则把栈顶的运算符出栈后连接到中缀表达式上。
  • 若运算符是右括号，栈顶是左括号时，删除栈顶运算符（清除括号。后缀表达式中是没有括号的，操作数后面的运算符的优先级由左向右降低）。
  • 重复以上过程直到遇到结束符。

问题的关键在于运算符优先级的比较，并且要考虑同一个运算符在栈内和栈外的级别。和前文计算中缀表达式时对运算符的优先级认定是一样的。

4.1 流程演示

如下把8+5*(7-1)-8/2 中缀表达式转换成后缀表达式。

  • 初始化运算符栈。

  • 扫描中缀表达式，字符8直接输出，+是第一个操作数，因可能后续有更高的运算符，入栈。

  • 字符5直接输出，*优先级大于栈顶+优先级，入栈。

  • (运算符在栈外优先级最高，入栈。

  • 字符7直接输出，因(运算符在栈内优先级最低，-运算符入栈。

  • 字符1直接输出，)栈外优先级最低。运算符出栈，一直碰到(。

  • -运算符小于栈中的+、+运算符。*、+运算符出栈。-入栈。

  • /优先级大于-，入栈。字符直接输出。

  • 字符扫描结束，把运算符栈中的运算符全部出栈。

4.2 编码实现

中缀表达式转后缀表达式的实现过程类似于中缀表达式的求值过程，只是不需要进行计算。或者说中缀表达式的求值过程包括了中缀表达式转换成后缀表达式以及对后缀表达式求值过程。

#include <iostream>
#include <stack>
#include <map>
#include <cmath>
#include <cstring>
using namespace std;
struct Opt {
	//运算符名字
	char name;
	//栈内级别
	int stackInJb;
	//栈外级别
	int stackOutJb;
	Opt(char name,int in,int out) {
		this->name=name;
		this->stackInJb=in;
		this->stackOutJb=out;
	}
	/*
	*栈外运算符和栈内运算比较
	*/
	bool compare(Opt* opt) {
		return this->stackOutJb > opt->stackInJb;
	}
	//显示
	void desc() {
		cout<<this->name<<"-"<<this->stackInJb<<"-"<<this->stackOutJb<<endl;
	}
};
map<char,Opt*> maps;

void mapOpt() {

	maps['^']=new Opt('^',3,4);
	maps['*']=new Opt('*',2,2);
	maps['/']=new Opt('/',2,2);
	maps['+']=new Opt('+',1,1);
	maps['-']=new Opt('-',1,1);
	maps['(']=new Opt('(',0,4);
	maps[')']=new Opt(')',-1,-1);

}

int main(int argc, char** argv) {
	mapOpt();
	//后缀表达式
	char hzExp[20]={'\0'};
	int j=0;
	stack<char> optStack;
	//中缀表达式
	char exps[20]="(8+5*(7-1)-8/2)";
	optStack.push(exps[0]);
	//栈内运算符
	Opt* opt;
	//栈外运算符
	Opt* opt_;
	for(int i=1; exps[i]!='\0' ; ) {

		if( !(exps[i]>='0' && exps[i]<='9')  ) {
			//栈内最初是 ) 运算符
			opt=maps[optStack.top()];
			//栈外运算符
			opt_=maps[exps[i]];

			if(opt_->name==')' && opt->name=='(') {
				//子表达式结束
				optStack.pop();
				i++;
				continue;
			}
			//比较
			bool com=opt_->compare(opt);

			if (com) {
				//入栈
				optStack.push(opt_->name);
				i++;
			} else  {
				//运算
				char n=opt->name;
				optStack.pop();
				hzExp[j]=n;
				j++;
			}

		} else {
			//数字字符
			hzExp[j]=exps[i];
			j++;
			i++;
		}
	}
	//hzExp[j]='\0';
	cout<<hzExp<<endl;
	return 0;
}

执行后输入结果：

当然，知道了如何把中缀表达式转成后缀表达式后，需要时，可以直接给出后缀表达式。

4. 总结

本文讲解了中缀、后缀表达式的求值过程以及如何将一个中缀表达式转换成后缀表达式。

本文同时收录在“编程驿站"公众号。

标签： # c++

留言评论

  • 这篇文章还没有收到评论，赶紧来抢沙发吧~