字首、中綴、字尾表達式
1.定義
所謂的前、中、後,是指表達式中運算符相對于運算對象的位置。
中綴
運算符位于運算對象中間,即是中綴表達式。如(1+2)*3-4
最普遍的、最易被人腦了解的是中綴表達式。
字首
運算符位于運算對象之前。即是字首表達式。
字尾
運算符位于運算對象之後,即是字尾表達式。如12+3*4-
2.總結
- 字首、字尾不易被人腦了解,但易于被計算機解析。
- 僅僅有對中綴表達式進行合理的轉換。才可得到對應的前、字尾表達式。
3.
3.1 中綴轉字首
過程例如以下:
(1) 初始化兩個棧:運算符棧S1和儲存中間結果的棧S2;
(2) 從右至左掃描中綴表達式。
(3) 遇到操作數時,将其壓入S2。
(4) 遇到運算符時。比較其與S1棧頂運算符的優先級:
(4-1) 假設S1為空。或棧頂運算符為右括号“)”。則直接将此運算符入棧。
(4-2) 否則。若優先級比棧頂運算符的較高或相等,也将運算符壓入S1。
(4-3) 否則,将S1棧頂的運算符彈出并壓入到S2中。再次轉到(4-1)與S1中新的棧頂運算符相比較;
(5) 遇到括号時:
(5-1) 假設是右括号“)”。則直接壓入S1;
(5-2) 假設是左括号“(”,則依次彈出S1棧頂的運算符。并壓入S2,直到遇到右括号為止,此時将這一對括号丢棄;
(6) 反複步驟(2)至(5),直到表達式的最左邊;
(7) 将S1中剩餘的運算符依次彈出并壓入S2;
(8) 依次彈出S2中的元素并輸出,結果即為中綴表達式對應的字首表達式。
3.2 對字首進行解析
所謂的解析。也就是求解表達式。
解析方法:
從右至左掃描表達式。遇到數字時。将數字壓入堆棧,遇到運算符時,彈出棧頂的兩個數,用運算符對它們做對應的計算(棧頂元素 op 次頂元素)。并将結果入棧;反複上述過程直到表達式最左端,最後運算得出的值即為表達式的結果。
比如字首表達式“-*+1234”:
(1) 從右至左掃描,将4、3、2、1依次壓入堆棧;
(2) 遇到+運算符,是以彈出1和2(1為棧頂元素,2為次頂元素,注意與字尾表達式做比較),計算出1+2的值,得3。再将3入棧;
(3) 接下來是*運算符,是以彈出3和3,計算出3*3=9,将9入棧;
(4) 最後是-運算符。計算出9-4的值。即5。由此得出終于結果。
3.3 中綴轉字尾
(2) 從左至右掃描中綴表達式;
(3) 遇到操作數時。将其壓入S2;
(4) 遇到運算符時,比較其與S1棧頂運算符的優先級:
(4-1) 假設S1為空,或棧頂運算符為左括号“(”,則直接将此運算符入棧;
(4-2) 否則,若優先級比棧頂運算符的高,也将運算符壓入S1(注意轉換為字首表達式時是優先級較高或同樣。而這裡則不包含同樣的情況);
(4-3) 否則,将S1棧頂的運算符彈出并壓入到S2中,再次轉到(4-1)與S1中新的棧頂運算符相比較;
(5-1) 假設是左括号“(”,則直接壓入S1;
(5-2) 假設是右括号“)”,則依次彈出S1棧頂的運算符,并壓入S2,直到遇到左括号為止,此時将這一對括号丢棄;
(6) 反複步驟(2)至(5),直到表達式的最右邊;
(8) 依次彈出S2中的元素并輸出。結果的逆序即為中綴表達式對應的字尾表達式(轉換為字首表達式時不用逆序)。
3.4 對字尾進行解析
與字首表達式相似。僅僅是順序是從左至右:
從左至右掃描表達式,遇到數字時,将數字壓入堆棧,遇到運算符時。彈出棧頂的兩個數,用運算符對它們做對應的計算(次頂元素 op 棧頂元素)。并将結果入棧;反複上述過程直到表達式最右端,最後運算得出的值即為表達式的結果。
比如字尾表達式“12+3*4-”:
(1) 從左至右掃描,将1和2壓入堆棧;
(2) 遇到+運算符。是以彈出2和1(2為棧頂元素,1為次頂元素。注意與字首表達式做比較),計算出1+2的值,得3,再将3入棧;
(3) 将3入棧;
(4) 接下來是*運算符。是以彈出3和3,計算出3*3=9,将9入棧;
(5) 将4入棧。
(6) 最後是-運算符,計算出9-4的值,即5。由此得出終于結果。
4.代碼:
#include <iostream>
#include <stack>
using namespace std;
double evaluate(double n1, char c, double n2)
{
switch (c)
{
case '+': return n1 + n2;
case '-': return n1 - n2;
case '*': return n1 * n2;
case '/': return n1 / n2;
}
}
int main(void)
{
//解析字首
char expr1[] = "-*+1234";
stack<double> sta;
int i = strlen(expr1) - 1;
int num1, num2;
char c;
do
{
c = expr1[i];
if (isdigit(c)) sta.push(c - '0');
else
{
num1 = sta.top();
sta.pop();
num2 = sta.top();
sta.pop();
sta.push(evaluate(num1, c, num2));
}
i--;
} while (i > -1);
cout << sta.top() << endl;
sta.pop();
//解析字尾
char expr2[] = "12+3*4-";
int n = strlen(expr2);
i = 0;
do
{
c = expr2[i];
if (isdigit(c)) sta.push(c - '0');
else
{
num1 = sta.top();
sta.pop();
num2 = sta.top();
sta.pop();
sta.push(evaluate(num2, c, num1));
}
i++;
} while (i < n);
cout << sta.top() << endl;
return 0;
}
char ops[] = "+-*/";
int get_op(char c)
{
for (int i = 0; i < 4; i++)
if (c == ops[i]) return i;
return -1;
}
/*
+ - * /
+ 0 0 -1 -1
- 0 0 -1 -1
* 1 1 0 0
/ 1 1 0 0
*/
int priority[4][4]=
{
{ 0, 0, -1, -1 },
{ 0, 0, -1, -1 },
{ 1, 1, 0, 0 },
{ 1, 1, 0, 0 }
};
int main(void)
{
//中綴轉字首
char expr[] = "1+((2+3)*4)-5";
stack<char> s1, s2;
int i, n;
char c;
i = strlen(expr) - 1; //從右向左掃描
do
{
c = expr[i];
if (isdigit(c)) s2.push(c); //數字直接壓棧s2
else
{
if (')' == c) s1.push(c); //遇到右括号,直接壓入棧s1
else if ('(' == c) //遇到左括号
{
while (')' != s1.top())
{
s2.push(s1.top());
s1.pop();
}
s1.pop();
}
else //其它非括号運算符
{
if (s1.empty() || ')' == s1.top()) s1.push(c);
else
{
while (!s1.empty() && (-1 == priority[get_op(c)][get_op(s1.top())]))
{
s2.push(s1.top());
s1.pop();
}
s1.push(c);
}
}
}
i--;
} while (i > -1);
while (!s1.empty()) //把s1中剩餘字元壓入s2
{
s2.push(s1.top());
s1.pop();
}
do
{
cout << s2.top();
s2.pop();
} while (!s2.empty());
return 0;
}
int main(void)
{
//中綴轉字尾
char expr[] = "1+((2+3)*4)-5";
stack<char> s1, s2;
int i, n;
char c;
i = 0; //從左至右掃描中綴表達式
n = strlen(expr);
do
{
c = expr[i];
if (isdigit(c)) s2.push(c); //數字直接壓棧s2
else
{
if ('(' == c) s1.push(c); //左括号
else if (')' == c) //右括号
{
while ('(' != s1.top())
{
s2.push(s1.top());
s1.pop();
}
s1.pop();
}
else
{
if (s1.empty() || '(' == s1.top()) s1.push(c);
else
{
while (!s1.empty() && (priority[get_op(c)][get_op(s1.top())]) <= 0)
{
s2.push(s1.top());
s1.pop();
}
s1.push(c);
}
}
}
i++;
} while (i < n);
while (!s2.empty()) //把s1中剩餘字元壓入s2
{
s1.push(s2.top());
s2.pop();
}
do
{
cout << s1.top();
s1.pop();
} while (!s1.empty());
return 0;
}
代碼下載下傳:字首、中綴、字尾表達式
全部内容的檔案夾
- CCPP Blog 檔案夾