0.前言
之前用js實現(xiàn)的一個簡易計算器有許多處理得不好的地方，拋開樣式的問題喷众，計算器最核心的計算部分直接使用了eval()函數，今天自己來實現(xiàn)計算部分拂檩，目標是獲取一個算式字符串，并讓計算機得出結果稻励。
在這之前，什么是中綴表達式望抽，什么是后綴表達式加矛？？
今天特地查閱了一下《數據結構教程》：
......在算術表達式中煤篙，運算符位于兩個操作數中間的表達式稱為中綴表達式（infix expression）...... 后綴表達式（postfix expression）或逆波蘭表達式，就是在算術表達式中運算符在操作數的后面......
我們在日常生活中所使用的幾乎都是中綴表達式辑奈。因為我們知道運算法則：括號內優(yōu)先計算，先乘除后加減......計算機并不懂得我們的計算法則妓羊，后綴表達式才對它的胃口稍计，轉化好的后綴表達式已經事先考慮了優(yōu)先級，不僅沒有括號臣嚣，而且位置越靠前的運算符越優(yōu)先執(zhí)行。
在達到我們的目標前硅则，我們事先準備三個“容器”：
var infixExp[]; //存放中綴表達式字符
var postfixExp[]; //存放后綴表達式字符
var tempExp[]; //存放臨時字符
備注：上面的數組應該理解成棧，js中數組的pop()和push()方法弹灭，下文會以出棧揪垄，入棧來稱呼。
1.從一個算式說起
4.25*（3+1）
看到這個算式饥努，我們的第一個問題來了，如何將其正確地存入到infixExp里酷愧？
也就是說我們需要的是['4.25','*','(','3','+','1',')']而不是['4','.','2','5','*','(','3','+','1',')']。
這里提供一種思路:
strTemp = "獲取到的中綴表達式字符串";
function expSolve() {
var i=0;
var j=0;
if(strTemp[0] == '-'){
i = 1;
}//對負數的處理
for(; i<strTemp.length; i++){
if(strTemp[i]=='('&&strTemp[i+1]=='-'){
infixExp.push('(');
j = i+1;
i++;
continue;
}//對負數的處理
if(strTemp[i]=='+'||strTemp[i]=='-'||strTemp[i]=='*'||strTemp[i]=='/'||strTemp[i]=='('||strTemp[i]==')'){
if(strTemp.slice(j, i)!='')
infixExp.push(strTemp.slice(j, i));
infixExp.push(strTemp[i]);
j=i+1;
}
}
if(strTemp.slice(j)!='')
infixExp.push(strTemp.slice(j));
}
掃描字符串的每個字符乍迄，當遇到運算符和括號時+，-褥伴，*，/漾狼，（，）時逊躁，將該符號前部分和該符號依次插入到infixExp里，要做是否為空的判斷(例如括號前可能會出現(xiàn)運算符)核芽。最后剩下部分可能為運算符右側的數也要插入數組酵熙。
可能還存在bug，慎用绿店！一定有更好的方法
2.中綴表達式轉換為后綴表達式
掃描infixExp中的每個元素：
- 遇到數庐橙，直接入棧
postfixExp。 - 遇到符號
+,-,*,/時：- 如果此時臨時棧
tempExp為空转培，該符號直接入棧tempExp浆竭。 - 如果此時臨時棧
tempExp不為空，該符號優(yōu)先級高于tempExp中的棧頂元素或棧頂元素為(時删窒，入棧tempExp顺囊。 - 如果此時臨時棧
tempExp不為空，該符號優(yōu)先級低于tempExp中的棧頂元素特碳，將tempExp中的棧頂元素出棧晕换，并入棧postfixExp站宗，直到該符號優(yōu)先級高于tempExp的棧頂元素或棧頂元素為(，才將該符號入棧夷家。
- 如果此時臨時棧
- 遇到括號
(或)時：
- 遇到左括號
(或辖，直接入棧tempExp。 - 遇到右括號
)颂暇，右括號兩個棧均不入，將tempExp中的棧頂元素出棧湿蛔，并入棧postExp县爬，直到遇到(。左括號只出棧但不進入postfixExp财喳。
左括號只有當遇到右括號時才出棧。
掃描完infixExp中的所有元素后扎瓶，將tempExp中的元素依次彈出入棧postfixExp
中綴轉后綴的實現(xiàn)（js）
function infixTopostfix() {
var item;
for (var i = 0; i < infixExp.length; i++) {
if (!isNaN(infixExp[i])) {
postfixExp.push(infixExp[i]);
}
else if (infixExp[i] == '+' || infixExp[i] == '-' || infixExp[i] == '*' || infixExp[i] == '/'||infixExp[i]=='('||infixExp[i]==')'){
if (tempExp.length == 0) {
tempExp.push(infixExp[i]);
}
else if (infixExp[i] == '*' || infixExp[i] == '/') {
item = tempExp.pop();
if (item == '*' || item == '/') {
postfixExp.push(item);
}
else {
tempExp.push(item);
}
tempExp.push(infixExp[i]);
}
else if (infixExp[i] == '+' || infixExp[i] == '-') {
while (tempExp.length != 0) {
item = tempExp.pop();
if(item == '('){
tempExp.push(item);
break;
}
postfixExp.push(item);
}
tempExp.push(infixExp[i]);
}
else if(infixExp[i] == '('){
tempExp.push(infixExp[i]);
}
else if(infixExp[i] == ')'){
while (1) {
item = tempExp.pop();
if(item == '('){
break;
}
postfixExp.push(item);
}
}
}
}
while (tempExp.length != 0) {
postfixExp.push(tempExp.pop());
}
}
3.后綴表達式的計算
掃描postfixExp中的每個元素：
- 遇到數概荷，入棧
tempExp碌燕。 - 遇到符號
+,-,*,/（后綴表達式一定不會含左右括號），從tempExp中依次取出兩個數修壕，并根據符號計算（后取出的數在符號左側）。最后將該次結果入棧tempExp改鲫。
掃描結束，tempExp中只剩一個元素像棘， 即為最終結果！
后綴表達式的計算（js）
function postfixCalc() {
for (var i = 0; i < postfixExp.length; i++) {
if (!isNaN(postfixExp[i])) {
tempExp.push(postfixExp[i]);
}
else {
var strRight = opeStack.pop();
var strLeft = opeStack.pop();
switch (postfixExp[i]) {
case '+':
opeStack.push(Number(strLeft) + Number(strRight));
break;
case '-':
opeStack.push(Number(strLeft) - Number(strRight));
break;
case '*':
opeStack.push(Number(strLeft) * Number(strRight));
break;
case '/':
opeStack.push(Number(strLeft) / Number(strRight));
break;
default:
alert("運算符號出錯截歉！");
}
}
}
var out = tempExp.pop(); //out即為最終結果
}
