后缀表达式的计算

没有考虑括号
从左往右依次读取，如果读到数字就入栈，如果读到符号就从栈中取出两个值进行计算。在后缀表达式的计算中先出栈的为后操作数b，先出栈的为前操作数a。还要注意判断除数为零的情况。
判断数组读到末尾  exp[i]!='\0' 注意斜杠的方向
下面是书本上的代码，使用顺序表写的

#include <iostream>
#define maxSize 100
using namespace std;
int op(int a,char Op,int b)
{
	if(Op=='+') return a+b;
	if(Op=='-') return a-b;
	if(Op=='*') return a*b;
	if(Op=='/')
	{
		if(b==0)
		{
			cout << "ERROR" << endl;
		}
		else
		{
			return a/b;
		}
	}
}
int com(char exp[])
{
	int i,a,b,c;
	int stack[maxSize];
	int top=-1;
	char Op;
	for(i=0;exp[i]!='\0';++i)
	{
		if(exp[i]>='0'&&exp[i]<='9')
		{
			stack[++top]=exp[i]-'0';
		}
		else
		{
			Op=exp[i];

			b=stack[top--];
			a=stack[top--];
			c=op(a,Op,b);
			stack[++top]=c;

		}
	}
	return stack[top];
}
int main()
{
	char a[]="2312+*+";
	cout << com(a) << endl;//答案应该为11 
	return 0;
}


原本感觉用链栈会更清晰，结果写出来后发现顺序栈代码量感觉更少，下面是自己用链栈的解法

#include <iostream>
#include <stdlib.h>
#include <ctype.h>
using namespace std;
typedef struct Node
{
	char data;
	struct Node *next;
}Node;
void push(Node *lst,char x)
{
	Node *p;
	p=(Node *)malloc(sizeof(Node));
	p->data=x;
	
	p->next=lst->next;
	lst->next=p;
}
int pop(Node *lst,char &x)
{
	if(lst->next==NULL)
		return 0;
	Node *p;
	p=lst->next;
	x=p->data;
	lst->next=p->next;
	free(p);
	return 1;
}
void cal(char *str,int l)
{
	Node *head;
	head=(Node *)malloc(sizeof(Node));
	head->next=NULL;
	Node *p=head;
	char a,b;
	for(int i=0;i<l;i++)
	{
		if(isdigit(str[i]))
		{
			push(p,str[i]);
		}
		if(ispunct(str[i]))
		{
			pop(p,b);
			pop(p,a);  //首先出栈的是第二操作数 
			if(str[i]=='+')
			{
				push(p,a+b-'0');
			}else if(str[i]=='-')
			{
				push(p,a-b+'0');
			}else if(str[i]=='*')
			{
				push(p,(a-'0')*(b-'0')+'0');
			}else if(str[i]=='/')
			{
				if(b-'0'==0)
				{
					cout << "ERROR" << endl;
					return;
				}
				else
				{
					push(p,(a-'0')/(b-'0')+'0');
				}
			}
		}
	}
	char f;
	pop(p,f);
	cout << f-'0' << endl;
}
int main()
{
	cal("2312+*+",7);//答案应该为11 
	return 0;
}

一.后缀表达式的计算 

后缀表达式： 

  指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行。（不再考虑运算符的优先规则）。

中缀表达式： 

   也就是我们日常最容易见到的表达式，从左至右考虑运算符的优先原则。

首先，我们以电脑的思维计算后缀表达式，这里必须用到栈的知识，栈通俗来讲就像一个桶，它里边存放的东西必须满足先进后出的原则。

我们以表达式1  2   4  8   2   -  7   4   -   /   *    +    *为例讲解。

         **后缀表达式用栈计算的原则就是遇到数字就入栈，遇到运算符就把栈顶两数字计算，再把计算结果入栈，这样反复直到栈空。**


具体过程如下： 

        第一步：1，2，4，8，2按顺序进栈，遇减号，栈顶2做减数，8做被减数，相减得6入栈 


                    第二步：7，4按顺序进栈，遇减号 ，栈顶4做减数，7做被减数，相减得3入栈 


        第三步： 遇除号，栈顶3作为除数，6作为被除数，运算得2入栈  


  第四步：遇乘号，栈顶元素2，4相乘得8入栈 


  第五步：遇加号，栈顶元素8，2相乘得10入栈 


   第六步：遇乘号，栈顶元素10，1相乘得10入栈 


第七步：输出栈底元素10，即该后缀表达式结果为10

以上就是后缀表达式求解的思想 
二.中缀表达式与后缀表达式的转换

对于中缀表达式与后缀表达式的转换有一个简便方法，就是先用括号按运算符优先级把中缀表达式一层一层括起来，每遇到一个括号，就把括号里面的运算符放在本层括号外边,直到把所有的运算符都都放在括号外边，再把括号去掉，得到的表达式就是对应的后缀表达式。

例如：x=a+b*(c-d)/e

        x = a + ( b * ( c - d) ) / e

        x = a + （ (b * ( c - d ) ) / e )

        x = (  (a + ( ( b * ( c - d ) ) / e ) )

       x = (  (a + ( b * (c d )- ) ) / e ) )

       x = ( (  a  + ( b (c d)- ) * ) / e) )

         x = ( ( a  ( b (c d) - ) * ) e ) / )+

       ( x  ( ( a ( b) c d ) - ) * ) e ) / ) + ) =

最后把括号去掉：x a b c d - * e / + =  


其实按这个方法真的是既简单又不容易错，希望可以帮助到大家，如果有什么错误，也欢迎大家指出，谢谢。

欢迎大家批评纠正
中缀表达式转后缀表达式 以及 后缀表达式的计算
一、中缀表达式 转 后缀表达式
步骤：

1.准备两个空栈S1，S2
2.当遇到数字直接压入S1
3.当遇到操作符号，如果S2为空，或者当前符号的优先级大于S2栈顶操作符优先级，或者遇到‘（’左括号，或者S2栈顶为‘（’左括号，当前操作符直接压入S2
4.当遇到操作符，如果当前操作符的优先级小于等于S2栈顶操作符的优先级，S2弹出栈顶，压入S1，直到S2为空，或者为左括号‘（’，或者为优先级小于当前符号优先级，将当前符号压入S2
5.当遇到右括号‘）’，S2弹出栈顶，压入S1直到弹出左括号‘（’，将括号略去
6.最后将S2栈顶弹出，压入S1，直到S2为空；
此时S1储存的相反顺序即为后缀表达式
例子：
将 1+（3-4x2+5）/2  转化为后缀表达式：
首先，拿来两个空栈S1、S2，按顺序从遍历式子。

‘1’是数字，直接压入S1；

‘+’是符号，S2为空，压入S2；

‘（ ’左括号直接压入S2；

‘3’是数字，直接压入S1；

‘-’是符号，S2栈顶为‘（’，将‘-’直接压入S2；

‘4’是数字，直接压入S1；

‘x’是符号，S2栈顶为‘-’，优先级 ‘x’ > ‘-’,将‘x’压入S2；

‘2’是数字，直接压入S1；

‘+’是符号，S2栈顶为‘x’，优先级 ‘x’ > ‘+’，弹出S2栈顶，压入S1，直到S2栈顶 优先级 小于 ‘+’，将‘+’压入S2；

‘2’是数字，直接压入S1；

‘）’遇到右括号，开始不断 将S2栈顶弹出，压入S1；知道遇到左括号，之后舍弃括号；

‘/’是符号，S2栈顶为‘-’，优先级 ‘/’ > ‘-’,将‘x’压入S2；

之后，依次弹出S2栈顶，压入S1，知道S2为空；

之后，依次弹出S1栈顶，压入S2，知道S1为空；

之后，依次弹出S2栈顶，输出；

此时输出序列为：


1 3 4 2 x - 5+2 / +

这就是1+（3-4x2+5）/2的后缀表达式。

//中缀表达式转后缀表达式
#include<iostream>
#include<string>
#include<stack>
using namespace std;

int to_int(char c){
	return c - '0';
}
int to_r(char c){//计算优先级
	if (c == '+' || c == '-')return 1;
	else if (c == '*' || c == '/')return 2;
}
int main(){
	stack<char> s1, s2;
	string str; cin >> str;
	for (int i = 0; i < str.length(); i++){
		if (str[i] >= '0'&&str[i] <= '9'){
			s1.push(str[i]);
		}
		else{
			if (s2.empty()||str[i] == '('){//判断s2是否为空 必须优先判断
				s2.push(str[i]);
			}
			else if (str[i] == ')'){   //其次，当前是否为 右括号 必须优先
				while (s2.top() != '('){
					s1.push(s2.top());
					s2.pop();
				}
				s2.pop();
			}
			else if (s2.top() == '('||to_r(str[i])>to_r(s2.top())  ){
				s2.push(str[i]);
			}		
			else if (to_r(str[i]) <= to_r(s2.top())){
				while (!s2.empty() && to_r(str[i]) <= to_r(s2.top())){
					s1.push(s2.top());
					s2.pop();
					if (s2.top() == '(')break;
				}
				s2.push(str[i]);
			}
		}
	}
	while (!s2.empty()){
		s1.push(s2.top());
		s2.pop();
	}
	while (!s1.empty()){
		s2.push(s1.top());
		s1.pop();
	}
	while(!s2.empty()){
		cout << s2.top() << " ";
		s2.pop();
	}

	system("pause");
	return 0;
}

二、 后缀表达式 的计算
步骤：

1.重新拿来一个 栈s3；

2.将上述s2栈顶弹出，压入s3，直到遇到 操作符；

3.用s3栈顶的下一位 加/减/乘/除 栈顶 ，将结果压入s3；

3.如此直到s2为空，s3此时只有一个元素，即为后缀表达式的运算结果；
例子：
上述后缀表达式 1 3 4 2 x - 5+2 / +

1入栈，3入栈，4入栈，2入栈，x 计算4x2 得8，入栈。

此时栈中元素为 1 3 8 （8为栈顶）;

‘-’ 计算 3-8 得 -5 入栈， 此时栈元素为 1  -5 （-5为栈顶）

5入栈，+ 计算-5 +5 得0 入栈， 此时栈元素为 1 0 （0为栈顶）

2入栈，/ 计算0/2 得 0 入栈，此时栈元素为 1 0 （0为栈顶）

‘+’计算1+0得1     即为后缀表达式得结果；
代码
//中缀表达式转后缀表达式  以及 后缀表达式的计算
#include<iostream>
#include<string>
#include<stack>
using namespace std;

int to_int(char c){
	return c - '0';
}
int to_r(char c){//计算优先级
	if (c == '+' || c == '-')return 1;
	else if (c == '*' || c == '/')return 2;
}
int op(int a, int b, char c){ //计算
	if (c == '+')return a + b;
	else if (c == '-')return a - b;
	else if (c == '*')return a*b;
	else if (c == '/')return a / b;
}
int main(){
	stack<char> s1, s2;
	string str; cin >> str;
	for (int i = 0; i < str.length(); i++){
		if (str[i] >= '0'&&str[i] <= '9'){
			s1.push(str[i]);
		}
		else{
			if (s2.empty()||str[i] == '('){
				s2.push(str[i]);
			}
			else if (str[i] == ')'){
				while (s2.top() != '('){
					s1.push(s2.top());
					s2.pop();
				}
				s2.pop();
			}
			else if (s2.top() == '('||to_r(str[i])>to_r(s2.top())  ){
				s2.push(str[i]);
			}		
			else if (to_r(str[i]) <= to_r(s2.top())){
				while (!s2.empty() && to_r(str[i]) <= to_r(s2.top())){
					s1.push(s2.top());
					s2.pop();
					if (s2.top() == '(')break;
				}
				s2.push(str[i]);
			}
		}
	}
	while (!s2.empty()){
		s1.push(s2.top());
		s2.pop();
	}
	while (!s1.empty()){
		s2.push(s1.top());
		s1.pop();
	}
	
	stack<int> s3;
	while (!s2.empty()){
		if (s2.top() >= '0'&&s2.top() <= '9'){
			s3.push(to_int(s2.top()));
			s2.pop();
		}
		else{
			int a = s3.top(); s3.pop();
			int b = s3.top(); s3.pop();
			int c = op(b, a, s2.top());
			s2.pop();
			s3.push(c);
		}
	}
	cout << s3.top() << endl;
	system("pause");
	return 0;
}

一、中缀表达式转化为后缀表达式
1.规则


从头到尾读取，对不同的对象操作不同


数字：直接输出


左括号（：直接压入堆栈，不用管优先级，但在左括号压入堆栈之后，左括号默认为优先级最低


右括号）：遇到右括号以后就一个一个pop运算符，直到遇到左括号，把右括号pop以后停止操作


运算符：

与栈顶运算符比较：大于压栈，小于等于将栈顶pop（while）


所有的处理完后，把堆栈中的一个一个输出


2.例题


解析：


二、后缀表达式的计算
1.规则


碰到数字：放进栈中


碰到运算符：取出栈顶的两个数字利用运算符进行运算后的到结果再压入栈中


2.例题
以上面的后缀表达式的计算过程为例：2 6 3 / 4 + * 5 -

过程：