数据结构：表达式求值（java版本）包括中缀表达式求值，后缀表达式求值（逆
波兰表达式求值）。。。
表达式求值
⾸先，⼤家可能不知道前缀表达式和中缀表达式，后缀表达式是什么，其有什么区别呢。我先简单介绍⼀下：
前缀表达式是⼀种没有括号的算术表达式，与中缀表达式不同的是，其将运算符写在前⾯，操作数写在后⾯。为纪念其发明者波兰数学家Jan Lukasiewicz，前缀表达式也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)
中缀表达式及我们正常的式⼦eg:1-(2+3)
后缀表达式： 逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）eg:1-(2+3) 1 2 3+ -
中缀表达式求值
中缀表达式即我们正常的表达式，我们先讲⼀下其求值规则：
1.通过⼀个index值（索引），来完成我们的表达式
2.如果我们发现是⼀个数字，就直接⼊数栈
3.如果我们发现是⼀个符号，分⼀下情况
3.1.如果发现当前的符号栈为空，就直接⼊栈
3.2.如果符号栈中有操作符，就进⾏⽐较，如果当前操作符的优先级⼩于或者等于栈中的操作符，就需要从数栈中pop出⼀个符号，进
⾏运算，将得到的结果⼊数栈，然后将当前的操作符⼊符号栈，如果当前操作符的优先级⼤于栈中的操作符，就直接⼊符号栈。如果有括号 先将左括号⼊栈 碰到右括号的时候，将符号栈中栈顶元素出栈，数字栈中两次出栈顶元素，进⾏运算，将运算的结果插⼊数字栈中， 直到为右括号便停⽌该循坏 并移除符号栈中的左括号
4.当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并进⾏运算。
5.最后在数栈只有⼀个数字，就是表达式的结果
⾸先我们来模拟⼀下：
⽐如：(3+4)*5-2
⾄此步骤结束，⼤家可以⾃⼰多模拟⼏遍。
代码：
⾸先我模拟了⼀个栈，⾥⾯添加了关于优先级的判断和是否为运算符号的判断，⼤家可以以只看这两种⽅法即可。
class ArrayStack{
private int maxSize;//栈的⼤⼩
private int[] stack;//数组，存放数据
private int top=-1;//top表⽰栈顶，初始化为-1
public ArrayStack(int maxSize){
this.maxSize=maxSize;
stack=new int[maxSize];
}
//栈满
public boolean isFull(){
return top==maxSize-1;
}
//栈空
public boolean isEmpty(){
return top==-1;
}
//⼊栈
public void push(int data){
if(isFull()){
System.out.println("栈满，插⼊失败");
return;
}
stack[++top]=data;
}
//出栈
public int pop(){
if(isEmpty()){
System.out.println("栈空，⽆元素");
return-1;
}
int data=stack[top];
top--;
return data;
}
//获取顶端元素
public int peek(){
return stack[top];
}
//显⽰栈的情况(遍历栈，从上往下)
public void list(){
if(isEmpty()){
System.out.println("栈空");
System.out.println("栈空");
return;
}
for(int i = top; i >=0; i--){
System.out.print(stack[i]+" ");
}
}
//⽤于判断优先级在进⾏表达式运算时需要⽤到
public int priority(int oper){
if(oper=='*'||oper=='/'){
return1;//优先级最⾼
}
else if(oper=='+'||oper=='-'){
return0;
}
else return-1;
}
//判断是不是⼀个运算符
public boolean isOper(char val){
return val=='+'||val=='-'||val=='*'||val=='/'||val=='('||val==')';
}
//计算⽅法
public int cal(int num1,int num2,int oper){
int res=0;
switch(oper){
case'+':
res=num1+num2;
break;
case'-':
res=num2-num1;
break;
case'*':
res=num1*num2;
break;
case'/':
res=num2/num1;
break;
default:break;
}
return res;
}
}
public class ComputerDemo {
public static void compute(String expression){
ArrayStack numStack=new ArrayStack(10);
ArrayStack operStack=new ArrayStack(10);
int index=0;
int num1=0;//表⽰输出数字的栈顶元素
int num2=0;//表⽰地如此输出数字栈的栈顶元素
int oper=0;//运算符号符号栈的栈顶元素
int res=0;//计算结果
char ch=' ';//将每次扫描得到的char保存到ch
String keepNum="";//防⽌不⽌⼀个数字为多位数
//开始while循环的扫描expression
while(index!=expression.length()){
//依次得到expression的每⼀个字符
ch = expression.substring(index, index +1).charAt(0);
//判断ch是什么，然后做相应的处理
if(operStack.isOper(ch)){
/**
*  3.1.如果发现当前的符号栈为空，就直接⼊栈
正则表达式获取括号内容
*  3.2.如果符号栈中有操作符，就进⾏⽐较，如果当前操作符的
*    优先级⼩于或者等于栈中的操作符，就需要从数栈中pop出⼀个符号，
*    进⾏运算，将得到的结果⼊数栈，然后将当前的操作符⼊符号栈，如果当前操作符
*    进⾏运算，将得到的结果⼊数栈，然后将当前的操作符⼊符号栈，如果当前操作符
*    的优先级⼤于栈中的操作符，就直接⼊符号栈
*
*    如果有括号先将左括号⼊栈碰到右括号的时候，将符号栈中栈顶元素出栈，数字栈中两次出栈顶元素，进⾏运算，                *    将运算的结果插⼊数字栈中，直到为右括号便停⽌该循坏并移除符号栈中的左括号
*/
if(ch=='('){
operStack.push(ch);
}
else if(ch==')'){
//获取符号并进⾏运算进⾏消括号操作
while(operStack.peek()!='('){
oper=operStack.pop();
num1 = numStack.pop();
num2 = numStack.pop();
res = numStack.cal(num1, num2, oper);
//把运算结果⼊数栈
numStack.push(res);
}
operStack.pop();//去掉左括号
}
else if(!operStack.isEmpty()){
//判断当前符号栈是否为空
if(operStack.priority(ch)<= operStack.priority(operStack.peek())){
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
//把运算结果⼊数栈
numStack.push(res);
//然后将当前的操作符⼊符号栈
operStack.push(ch);
}
else{
//如果当前的操作符的优先级⼤于栈中的操作符，就直接⼊符号栈
operStack.push(ch);
}
}else{
//如果为空则直接⼊符号栈
operStack.push(ch);
}
}
else{//如果是数，则直接⼊数栈
keepNum+=ch;
//如果ch已经是最后⼀位，则直接⼊栈
if(index==expression.length()-1){
numStack.push(Integer.parseInt(keepNum));
}else{
//判断下⼀位是不是数字，如果是数字，就继续扫描，如果是运算符则⼊栈
//注意看后⼀位，不是index++
if(operStack.isOper(expression.substring(index+1,index+2).charAt(0))){
/
/如果后⼀位是运算符，则⼊栈keepNum="1" "123"
numStack.push(Integer.parseInt(keepNum));
// keepNum清空
keepNum="";
}
}
}
//让index+1，并判断是否扫描到expression最后
index++;
}
//当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运⾏
while(!operStack.isEmpty()){
num1=numStack.pop();
num2=numStack.pop();
oper=operStack.pop();
res=numStack.cal(num1,num2,oper);
res=numStack.cal(num1,num2,oper);
numStack.push(res);
}
//将数栈的最后数，pop出，就是结果
int res2=numStack.pop();
System.out.printf("表达式%s = %d",expression,res2);
}
public static void main(String[] args){
String expression="(2-4)+3*6";
compute(expression);
}
}
中缀表达式转后缀表达式
⼤家可能会想：既然中缀表达式可以计算结果，我们为什么还要学习后缀表达呢？ ⽽且后缀表达式看起来不容易理解：后缀表达式是计算机通常⽤的⽅法，因为它不⽤考虑优先级，可以直接进⾏出栈运算即可。
所以我们先学习⼀下如何使中缀表达式转化为后缀表式。
需要了解其法则：
中缀转后缀表达式
1.初始化两个栈，运算栈S1和存储中键结果的栈s2
2.从左⾄右扫描中缀表达式
3.遇到操作数时，将其压s2
4.遇到运算符时，⽐较其与s1栈顶运算符的优先级
4.1） 如果s1为空，或栈顶运算符为左括号，则直接将此运算符⼊栈
4.2)否则，如果优先级⽐栈顶运算符的⾼，也将运算符压⼊s1.
4.3)否则，将s1栈顶的运算符弹出并压⼊到s2中，再次转到4.1与s1中新的栈顶运算符相⽐较
5.遇到括号时：
5.1）如果是左括号，则直接⼊栈
5.2）如果是右括号，则依次弹出s1栈顶的运算符，并压⼊s2，直到遇到左括号为⽌，此时将这⼀对括号丢弃
6)重复步骤2-5 直到表达式的最右边
7）将s1剩余的运算符依次弹出并压⼊s2
8）依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。