一、概念

算术表达式是由操作数（运算数）、运算符（操作符）、和界线符（括号）三部分组成，在计算机中进行算术表达式的计算是通过堆栈来实现的。

二后缀表达式的逻辑和实现方式（逆波兰表达式求值）

1.定义
如果每个操作符跟在它的两个操作数之后，而不是两个操作数之间，那么这个表达式就是后缀表达，又称为逆波兰表达式，如：3 5 + 7 * 1 -

2.后缀表达式计算机求值
1.与前缀表达式类似，只是顺序是从左至右：
2.从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，其中先出栈的是右操作数，后出栈的是左操作数，
3.用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；
4.重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

3.例子
计算后缀表达式的值：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为最终结果

三代码实现：

#include<iostream>
using namespace std;
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAXSIZE 100
#define ok 1
#define error 0
#define ovrflow -1
typedef int status;
typedef struct number{// 数值 int data;struct number *next;
}number,*number1;
typedef struct signal{// 字符 char data;struct signal *next;
}sign,*sign1;
status push1(number1 &s,int elem);
status push2(sign1 &s,char elem);
status in(char elem);
int pop1(number1 &s);
int pop2(sign1 &s);
status gettop1(number1 s);
char gettop2(sign1 s);
int get_index(char str);
char precede(char a, char b);
int operate(int x,char a,int y);
char characters[7] = {'+', '-', '*', '/', '(', ')', '#'};
char priority[7][7] = {{'>', '>', '<', '<', '<', '>', '>'},{'>', '>', '<', '<', '<', '>', '>'},{'>', '>', '>', '>', '<', '>', '>'},{'>', '>', '>', '>', '<', '>', '>'},{'<', '<', '<', '<', '<', '=', ' '},{'>', '>', '>', '>', ' ', '>', '>'},{'<', '<', '<', '<', '<', ' ', '='}
}; // 各个运算符之间的优先级关系int get_index(char str)
{// 获取相应运算符的索引for(int i = 0; i < 7; i++){if(str==characters[i]) return i;}printf("未找到匹配的字符\n");
}char precede(char a, char b)
{ //获取两个运算符之间的优先级关系int x = get_index(a);int y = get_index(b);return priority[x][y];
}
int main(int argc, char** argv){while(1){number1 s1=NULL;sign1 s2=NULL;//初始化 int x,y,n,elem=0,flag=0,j,k=0;char *a=new char[100],c,m;while(1){cout<<"请输入表达式:";scanf("%s",a);x=strlen(a);push2(s2,'#');for(int i=0;i<x;i++){if(flag==1) break;if(a[i]!='#'||gettop2(s2)!='#')if(in(a[i])!=0){//如果是数值 k=0;k=k*10+(a[i]-48);i++;while(in(a[i])!=0){k=k*10+(a[i]-48);i++;}i--;push1(s1,k);}else {if(a[i]==' '){continue;}switch(precede(gettop2(s2),a[i])){case '<':push2(s2,a[i]);break;case '=':pop2(s2);break;case '>':c=pop2(s2);y=pop1(s1);n=pop1(s1);elem=operate(n,c,y);push1(s1,elem);i--;break;default:cout<<"该优先级不存在,表达式错误,请重新输入"<<endl;flag=1; }}} printf("%d\n",gettop1(s1));}}return 0;
}
status in(char c){if(c>=48&&c<=58){return ok;}return error;
}
status push1(number1 &s,int elem){number *p;p=new number;p->data=elem;p->next=s;s=p;return ok;
}
status push2(sign1 &s,char elem){sign *p;p=new sign;p->data=elem;p->next=s;s=p;return ok;
}
int pop1(number1 &s){int x;if(s==NULL) return error;number *p=s;s=s->next;x=p->data;delete p;return x;
}
int pop2(sign1 &s){char c;if(s==NULL) return error;sign *p=s;s=s->next;c=p->data;delete p;return c;
}
status gettop1(number1 s){if(s==NULL) return error;return s->data;
}
char gettop2(sign1 s){if(s==NULL) return error;return s->data;
}
int operate(int x,char a,int y){if(a=='+') return x+y;if(a=='-') return x-y;if(a=='*') return x*y;if(a=='/') return x/y;
}

四运算结果：