栈的应用之后缀表达式的求解

快来打我* 2022-09-25 14:20 106阅读 0赞

# 后缀表达式的求解 #

在小学的运算中，我们经常接触到的数学表达式，它的规则也就是老生常谈的了-"先乘除，后加减，从左到右，先括号后括号外"，但后来出现的四则运算，则要求优先级，计算更加复杂，而计算机解决这种问题的方法就是利用栈，这就引入了后缀表达式

**后缀表达式的基本概念:**

后缀表达式也叫逆波兰表达式，是一种不需要括号的后缀表达式(RPN),所有的运算符号都在数字的后面.

eg: 12 3 4 + \* 6 - 8 2 / +

**后缀表达式的求解规则：**

(1).从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到符号就将处于栈顶的两个数字出栈，进行相应的运算，运算结果再次进栈，最终栈顶的元素就是最终的计算结果

(2).当遇到符号将栈顶的两个数字出栈，先出栈的是右操作数，后出栈的为左操作数

就好像拿到武功秘籍一样，那仫具体情况如何呢？请看下图分析:

![Center][]

#pragma once
    #include<iostream>
    #include<stack>
    #include<cassert>
    #include<cstring>
    using namespace std;
    
    enum Symbol
    {
    	OP_NUM,
    	OP_SYMBOL,
    	ADD,
    	SUB,
    	SUL,
    	DIV,
    };
    
    struct Cell
    {
    	char _symbol;   //操作符
    	int _value;    //操作数
    };
    //12 3 4 + * 6 - 8 2 / + = 82
    //9 3 1 - 3 * + 10 2 / + =20
    void testMinToLast()
    {
    	stack<int> s;
    	Cell RPNArray[]=
    	{
    		//{OP_NUM,12},
    		//{OP_NUM,3},
    		//{OP_NUM,4},
    		//{OP_SYMBOL,ADD},
    		//{OP_SYMBOL,SUL},
    		//{OP_NUM,6},
    		//{OP_SYMBOL,SUB},
    		//{OP_NUM,8},
    		//{OP_NUM,2},
    		//{OP_SYMBOL,DIV},
    		//{OP_SYMBOL,ADD},
    
    		{OP_NUM,9},
    		{OP_NUM,3},
    		{OP_NUM,1},
    		{OP_SYMBOL,SUB},
    		{OP_NUM,3},
    		{OP_SYMBOL,SUL},
    		{OP_SYMBOL,ADD},
    		{OP_NUM,10},
    		{OP_NUM,2},
    		{OP_SYMBOL,DIV},
    		{OP_SYMBOL,ADD},
    	};
    	size_t sz=sizeof(RPNArray)/sizeof(RPNArray[0]);
    	for(size_t i=0;i<sz;i++)
    	{
    		int right=0,left=0;
    		if(RPNArray[i]._symbol == 0)
    		{
    			s.push(RPNArray[i]._value);
    		}
    		else
    		{
    			switch(RPNArray[i]._value)
    			{
    			case ADD:
    				right=s.top();
    				s.pop();
    				left=s.top();
    				s.pop();
    				s.push(left+right);
    				break;
    			case SUB:
    				right=s.top();
    				s.pop();
    				left=s.top();
    				s.pop();
    				s.push(left-right);
    				break;
    			case SUL:
    				right=s.top();
    				s.pop();
    				left=s.top();
    				s.pop();
    				s.push(left*right);
    				break;
    			case DIV:
    				right=s.top();
    				s.pop();
    				left=s.top();
    				s.pop();
    				s.push(left/right);
    				break;
    			default:
    				break;
    			}
    		}
    	}
    	cout<<s.top()<<endl;
    	s.pop();
    }
    
    int main()
    {
    	testMinToLast();
    	system("pause");
    	return 0;
    }

在知道了后缀表达式的求解之后，中缀表达式如何转为后缀表达式呢？

**中缀表达式转后缀表达式的规则：**

从左到右遍历中缀表达式的每个数字和符号，若是数字就输出；若是符号，则需要判断该符号与栈顶元素的优先级，如果是右括号或者优先级不高于栈顶符号(乘除优先加减)，则栈顶元素依次出栈并输出，并将当前符号进栈，一直到输出最终后缀表达式为止

![Center 1][]

待续...

[Center]: /images/20220717/8cfcf178f0374dca9edc13ccb0c1ddd0.png
[Center 1]: /images/20220717/a9cf7e7a95804e7781a86f0a69560300.png