栈与四则运算

时间:2022-12-15 20:42:44

上一篇也提到,栈其实是一种很重要的数据结构,下面简单讲解下栈是如何实现四则运算的。

在此之前,需要说明的是,很多编程语言在进行四则运算的时候,都不是直接运用中缀表达式进行运算的,一般会将中缀表达式转换为后缀表达式然后利用栈进行具体的运算。因为,计算机无法识别所谓的先乘除后加减的运算顺序的,而且,一旦出现括号的表达式,按照中缀表单时处理起来更困难,所以,一般来说,很多编程语言在进行四则运算的时候,都会讲中缀转换为后缀,因为,后缀(前缀也是)表达式有个很好的有点:它没有括号,结合顺序完全是按照符号出现的顺序进行的,所以无需考虑过多的其他问题。

一、前缀、中缀以及后缀表达式的概念

  1、首先说中缀,它最简单,就是我们平常写的算式。1+2*3-(4-2),这个我们平常用的算式书写方式就是中缀:中,代表符号是位于中间的,它进行和两边的数据进行结合并运算得出结果。

  2、后缀:符号位于两个数字之后,例如:1+2的后缀表达式就是1 2+;1+2*3的后缀表达式就是:1(23*)+;如果理解不了,看下面的丑图理解:

栈与四则运算

这里要注意的是:符号的结合顺序是从最左边那个符号(这里是*)进行结合的,例如:

123*-3+等价于2*3 - 1 + 3,具体看丑图;同样,前缀也遵循类似的原则,只不过它是从右往左结合(即最右边的符号优先结合)

栈与四则运算

 

记住:2*3是显式加上了括号的,为了方便理解,下面的式子涉及到乘除我也会自动为他们的运算加上括号。

  3、前缀:其实理解了后缀,前缀就很好理解了,前缀就是将符号放在数字的前面而已,结合的方式就是符号结合后面两个数字,例子

  2*3 - 1 + 3的前缀表达式为:+-*2 3 1 3(最右边符号优先结合);

 

二、中缀和后缀的转换

  例如以下的中缀表达式:((2-(3*5))-(4/2));(注意,算法显式加上括号)

  具体转化的方法是:遇到数字,直接输出;遇到左括号,直接忽略;遇到符号,将符号压入栈,遇到右括号则弹出栈中的符号。

  ok,下面的代码展示了这个过程:

//中缀表单时到后缀表达式的转换
public String change(String express){
String rtn = "";
char [] expressChar = express.toCharArray();
Stack<Character> stack = new Stack<Character>();
for(int i=0;i<expressChar.length;i++){
if(expressChar[i]<='9' && expressChar[i]>='0'){
//遇到数字,直接输出
rtn = rtn + expressChar[i];
}else if(expressChar[i]=='*' || expressChar[i]=='-' || expressChar[i]=='+' || expressChar[i]=='/'){
//遇到四则运算的符号,则直接压入栈
stack.push(expressChar[i]);
}else if(expressChar[i]==')'){
//如果是右括号,将栈中的元素pop出来
rtn = rtn + stack.pop();
}else{
//其他元素则忽略(左括号)
continue;
}
}
return rtn;
}

  当然,这种方法有一定的局限性:需要显式地加上括号才可以转换成功,所以忽略了一个步骤就是显式为表达式加上必须的括号。不过这不是我们讨论的主题,我们主要是用这个例子说明栈的一个典型作用罢了。

 

三、利用后缀表达式进行四则运算

  在三中,得到了四则运算式子的表达式之后,我们就可以运用栈进行四则运算了,而运算的方法是这样:在后缀表达式中,我们遇到操作数,则将操作数推进栈中,遇到操作符,则从栈中推出两个数字进行运算,并同时把运算结果推进栈中即可;循环以上步骤直到所有操作符以及操作数遍历完毕。

下面简单贴上该过程的代码:

//利用后缀表达式进行四则运算
public int operation(String suffix){
char [] suffixChar = suffix.toCharArray();
Stack<Character> stack = new Stack<Character>();
for(int i=0;i<suffixChar.length;i++){
if(suffixChar[i]<'9' && suffixChar[i]>'0'){
stack.push(suffixChar[i]);
}else {
switch (suffixChar[i]) {
case '+':
stack.push((char)(stack.pop()-'0' + stack.pop()-'0'));
break;
case '-':
stack.push((char)(stack.pop()-'0' - stack.pop()-'0'));
break;
case '*':
stack.push((char)((stack.pop()-'0') * (stack.pop()-'0')));
break;
case '/':
stack.push((char)((stack.pop()-'0') / (stack.pop()-'0')));
break;
}
}

}
return stack.pop();
}

  总而言之,栈是一个非常重要且基础的数据结构,很多计算机编程语言底层其实就提供了栈的原始实现。例如,我们在嵌套调用函数(例如递归)时,就是一个典型的入栈出栈过程:先被调用的函数最后才结束运算;后被调用的函数后面执行,栈充当中间存储数据和运算状态的角色,保证运算正常运算下去。