&web_id=" language="JavaScript">
Fork me on GitHub

用JavaScript实现中缀表达式计算器【1.0】

学习了栈结构,你以为学完了栈?今天要讲的是中缀表达式转后缀表达式,后缀表达式的计算和中缀表达式的计算,接下来让我们开始吧!

什么是中缀表达式和后缀表达式?

中缀表示法(或中缀记法)是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4)。与前缀表达式(例:+ 3 4)或后缀表达式(例:3 4 +)相比,中缀表达式不容易被电脑解析,但仍被许多程序语言使用,因为它符合人们的普遍用法。
与前缀或后缀记法不同的是,中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来,用于指示运算的次序。

后缀表示法 (逆波兰表示法)(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

逆波兰记法中,操作符置于操作数的后面。例如表达“三加四”时,写作“3 4 +”,而不是“3 + 4”。如果有多个操作符,操作符置于第二个操作数的后面,所以常规中缀记法的“3 - 4 + 5”在逆波兰记法中写作“3 4 - 5 +”:先3减去4,再加上5。使用逆波兰记法的一个好处是不需要使用括号。例如中缀记法中“3 - 4 5”与“(3 - 4)5”不相同,但后缀记法中前者写做“3 4 5 -”,无歧义地表示“3 (4 5 ) -”;后者写做“3 4 - 5 *”。
逆波兰表达式的解释器一般是基于堆栈的。解释过程一般是:操作数入栈;遇到操作符时,操作数出栈,求值,将结果入栈;当一遍后,栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现,并且能很快求值。

首先我们要进行的就是中缀表达式和后缀表达式的转换。开始吧!

中缀表达式转后缀表达式

首先让我们来了解一下有关中缀转后缀的算法,大概有以下几个规则:
(1)当读到数字直接送至输出队列中;
(2)当读到运算符t时:
a.将栈中所有优先级高于或等于t的运算符弹出,送到输出队列中;
  b.t进栈;
(3)读到左括号时总是将它压入栈中;
(4)读到右括号时,将靠近栈顶的第一个左括号上面的运算符全部依次弹出,送至输出队列后,再丢弃左括号;
(5)中缀表达式全部读完后,若栈中仍有运算符,将其送到输出队列中。

符号的优先级

首先我们必须知道有关运算符优先级的问题,经过查阅,我们可以得到如下二维数组。

1
2
3
4
5
6
7
8
9
var sign = new Array();
// + - * / ( ) #
sign[0] = new Array('1','1','-1','-1','-1','1','1'); //+
sign[1] = new Array('1','1','-1','-1','-1','1','1'); //-
sign[2] = new Array('1','1','1','1','-1','1','1'); //*
sign[3] = new Array('1','1','1','1','-1','1','1'); ///
sign[4] = new Array('-1','-1','-1','-1','-1','0',''); //(
sign[5] = new Array('1','1','1','1','','1','1'); //)
sign[6] = new Array('-1','-1','-1','-1','-1','','0'); //#

先找横行,代表栈中的运算符,再找纵行,代表你想要比较的运算符,-1代表栈中符号优先级小于栈外符号优先级,栈外符号入栈;1代表栈中符号优先级大于栈外符号优先级,栈中符号弹出,直到栈中符号优先级比栈外符号小,栈外符号入栈;0代表优先级一样,暂时不进行考虑。

符号的比较函数

弄清楚符号的优先级,我们就可以对两个符号进行比较,具体实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function Sign(a,b){
var str = ['+','-','*','/','(',')','#'];
var str1;
var str2;
for(var i=0;i<7;i++){
if(a == str[i]){
str1 = i;
}
if(b == str[i]){
str2 = i;
}
}
var count = sign[str1][str2];
return count;
}

将符号关系转换为数字更有利于我们之后的判断,接下来就是我们的正题来了。

构造一个栈

跟上一篇一样,我们需要构造一个基本的数据结构—-栈,来实现这个项目,不同的是,我们新增加了一个函数peek()来获取栈顶的第一个元素。下面是代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function Stack(){
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.length = length;
this.peek = peek;
this.clear = clear;
}
function push(element){
this.dataStore[this.top] = element;
this.top++;
}
function pop(){
return this.dataStore[--this.top];;
}
function peek(){
return this.dataStore[this.top-1];
}
function clear(){
this.top = 0;
}
function length(){
return this.top;
}

构造好一个栈之后,我们就需要进行最重要的步骤了,构造转换函数。

中缀表达式转换函数

中缀表达式转后缀表达式跟C语言不同,JavaScript是一种弱类型语言,它的实现更加的灵活,首先我们在栈中先压入#,令最后一个元素能够弹出,然后我们构造如下函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
function Change(item){
var str = item;
var stack = new Stack(); //构造一个栈
stack.push("#"); //将#压入栈中
var outStack = new Array(); //构造一个队列
var small = "";
var flog = 0;
for(var i=0;i<item.length;i++){
if(!isNaN(str[i]) || str[i] == '.'){ //如果是数字或者小数点进入循环
if(!isNaN(str[i+1]) || str[i+1] == '.' || flog == 1){
small = small + str[i];
flog = 1;
if(isNaN(str[i+1]) && str[i+1] != '.'){
outStack.push(parseFloat(small)); //将整个字符串转换成小数数值后入队
small = "";
flog = 0;
}
}
else{
outStack.push(str[i]);
}
}
else{
var txt = stack.peek();
if( str[i] == '('){ //遇到左括号直接入栈
stack.push(str[i]);
}
else if( str[i] == ')'){ //遇到右括号将栈中左括号之前的符号全部弹出入队,然后删去左括号
for(var j = i + 1 ; stack.peek() != "(" ; j--){
outStack.push(stack.pop());
}
stack.pop();
}
else{ //两个符号判断关系,选择入队或弹出操作
var relationship = Sign(txt,str[i]);
if( relationship == -1){
stack.push(str[i]);
}
else if(relationship >= 0){
do{
outStack.push(stack.pop());
}while(Sign(stack.peek(),str[i])>0);
stack.push(str[i]);
}
}
}
}
console.log(outStack);
}

然后我们就可以输入中缀表达式进行计算了,注意在控制台计算的时候在中缀表达式的后面加一个#号,防止栈内符号未完全弹出的情况出现。

测试实例:Change('1+2*(3-1+2)-3#');
示例输出:1231-2+*+3- 注意,输出的是一个队,也就是一个数组,本样例是为了方便这样测试的。

后缀表达式的计算

相对于中缀表达式转后缀表达式,后缀表达式的计算就简单多了,直接上代码,在注释中进行讲解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
function suffix(item){
var str = item;
var outStack = new Stack();
var small = "";
var flog = 0;
for(var i=0;i<item.length;i++){
if((!isNaN(str[i]) || str[i] == '.') && (str[i]!=',')){
if(!isNaN(str[i+1]) || str[i+1] == '.' || flog == 1){
small = small + str[i];
flog = 1;
if((isNaN(str[i+1]) && str[i+1] != '.') || (str[i+1]==',')){
outStack.push(parseFloat(small));
small = "";
flog = 0;
}
}
else{
outStack.push(str[i]);
}
}
else if(str[i]=='+' || str[i]=='-' || str[i]=='*' || str[i]=='/'){
var str1 = parseFloat(outStack.pop());
var str2 = parseFloat(outStack.pop());
switch(str[i]){
case'+':outStack.push(str2 + str1);
break;
case'-':outStack.push(str2 - str1);
break;
case'*':outStack.push(str2 * str1);
break;
case'/':
if(str1 == 0){
alert("对不起,被除数不能为0,请重试!")
}
outStack.push(str2 / str1);
break;
}
}
}
return outStack.peek().toFixed(2);
}

测试实例:suffix('1231-2+*+3-')
示例输出:6
注意后缀表达式的计算无需将符号入栈,只需要弹出数字进行运算即可。

中缀表达式的计算

中缀表达式的计算原理如果你理解了中缀转后缀、后缀运算那么很快你就能够理解,这个例子也是直接在代码中进行讲解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
function Infix(item){
var str = item;
var stack = new Stack();
stack.push("#"); //将#字压入栈
var outStack = new Array();
var small = "";
var flog = 0;
for(var i=0;i<item.length;i++){
if(!isNaN(str[i]) || str[i] == '.'){
if(!isNaN(str[i+1]) || str[i+1] == '.' || flog == 1){
small = small + str[i];
flog = 1;
if(isNaN(str[i+1]) && str[i+1] != '.'){
outStack.push(parseFloat(small));
small = "";
flog = 0;
}
}
else{
outStack.push(str[i]); //数字直接入栈
}
}
else{
var txt = stack.peek();
if( str[i] == '('){
stack.push(str[i]);
}
else if( str[i] == ')'){
for(var j = i + 1 ; stack.peek() != "(" ; j--){ //符号判断完不进行入栈操作,而是进行弹出运算
var a1 = parseFloat(outStack.pop());
var a2 = parseFloat(outStack.pop());
var a3 = stack.pop();
switch(a3){
case'+':outStack.push(a2 + a1);
break;
case'-':outStack.push(a2 - a1);
break;
case'*':outStack.push(a2 * a1);
break;
case'/':outStack.push(a2 / a1);
break;
}
}
stack.pop();
}
else{
var relationship = Sign(txt,str[i]);
if( relationship == -1){
stack.push(str[i]);
}
else if(relationship >= 0){
do{
var b1 = parseFloat(outStack.pop());
var b2 = parseFloat(outStack.pop());
var a3 = stack.pop();
switch(a3){
case'+':outStack.push(b2 + b1);
break;
case'-':outStack.push(b2 - b1);
break;
case'*':outStack.push(b2 * b1);
break;
case'/':outStack.push(b2 / b1);
break;
}
}while(Sign(stack.peek(),str[i])>0);
stack.push(str[i]);
}
}
}
}
console.log(outStack.pop().toFixed(5)); //将小数位数控制在5位小数,结束运算。
}

本代码可以自行尝试输出和输入,根据这个原理以及少许html和CSS的基础就能够写出相当不错的计算器
计算器的实现:神奇的计算器

今天的代码就到这里,谢谢大家!

Godlike Meteor wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
我知道不会有人点开,但万一真有人想不开呢?
------ 本文结束 ------