原文位址為: 中綴表達式轉換成字尾表達式并求值
算法:
中綴表達式轉字尾表達式的方法:
1.遇到操作數:直接輸出(添加到字尾表達式中)
2.棧為空時,遇到運算符,直接入棧
3.遇到左括号:将其入棧
4.遇到右括号:執行出棧操作,并将出棧的元素輸出,直到彈出棧的是左括号,左括号不輸出。
5.遇到其他運算符:加減乘除:彈出所有優先級大于或者等于該運算符的棧頂元素,然後将該運算符入棧
6.最終将棧中的元素依次出棧,輸出。
例如
a+b*c+(d*e+f)*g ----> abc*+de*f+g*+
遇到a:直接輸出:
字尾表達式:a
堆棧:空
遇到+:堆棧:空,是以+入棧
字尾表達式:a
堆棧:+
遇到b: 直接輸出
字尾表達式:ab
堆棧:+
遇到*:堆棧非空,但是+的優先級不高于*,是以*入棧
字尾表達式: ab
堆棧:*+
遇到c:直接輸出
字尾表達式:abc
堆棧:*+
遇到+:堆棧非空,堆棧中的*優先級大于+,輸出并出棧,堆棧中的+優先級等于+,輸出并出棧,然後再将該運算符(+)入棧
字尾表達式:abc*+
堆棧:+
遇到(:直接入棧
字尾表達式:abc*+
堆棧:(+
遇到d:輸出
字尾表達式:abc*+d
堆棧:(+
遇到*:堆棧非空,堆棧中的(優先級小于*,是以不出棧
字尾表達式:abc*+d
堆棧:*(+
遇到e:輸出
字尾表達式:abc*+de
堆棧:*(+
遇到+:由于*的優先級大于+,輸出并出棧,但是(的優先級低于+,是以将*出棧,+入棧
字尾表達式:abc*+de*
堆棧:+(+
遇到f:輸出
字尾表達式:abc*+de*f
堆棧:+(+
遇到):執行出棧并輸出元素,直到彈出左括号,所括号不輸出
字尾表達式:abc*+de*f+
堆棧:+
遇到*:堆棧為空,入棧
字尾表達式: abc*+de*f+
堆棧:*+
遇到g:輸出
字尾表達式:abc*+de*f+g
堆棧:*+
遇到中綴表達式結束:彈出所有的運算符并輸出
字尾表達式:abc*+de*f+g*+
堆棧:空
例程:
這是我自己寫的一個簡單的中綴表達式求值程式,簡單到隻能計算10以内的數,支援+-*/()運算符。
#include <stack>
using namespace std;
bool IsOperator(char ch)
{
char ops[] = "+-*/";
for (int i = 0; i < sizeof(ops) / sizeof(char); i++)
{
if (ch == ops[i])
return true;
}
return false;
}
//
// 比較兩個操作符的優先級
int Precedence(char op1, char op2)
{
if (op1 == '(')
{
return -1;
}
if (op1 == '+' || op1 == '-')
{
if (op2 == '*' || op2 == '/')
{
return -1;
}
else
{
return 0;
}
}
if (op1 == '*' || op1 == '/')
{
if (op2 == '+' || op2 == '-')
{
return 1;
}
else
{
return 0;
}
}
}
//
// 中綴表達式轉換成字尾表達式
void inFix2PostFix(char* inFix, char* postFix)
{
int j = 0, len;
char c;
stack<char> st;
len = strlen(inFix);
for (int i = 0; i < len; i++)
{
c = inFix[i];
if (c == '(')
st.push(c);
else if (c == ')')
{
while (st.top() != '(')
{
postFix[j++] = st.top();
st.pop();
}
st.pop();
}
else
{
if (!IsOperator(c))
st.push(c);
else
{
while (st.empty() == false
&& Precedence(st.top(), c) >= 0)
{
postFix[j++] = st.top();
st.pop();
}
st.push(c);
}
}
}
while (st.empty() == false)
{
postFix[j++] = st.top();
st.pop();
}
postFix[j] = 0;
}
//
// 字尾表達式求值程式
double postFixEval(char* postFix)
{
stack<char> st;
int len = strlen(postFix);
char c;
for (int i = 0; i < len; i++)
{
c = postFix[i];
if (IsOperator(c) == false)
{
st.push(c - '0');
}
else
{
char op1, op2;
int val;
op1 = st.top();
st.pop();
op2 = st.top();
st.pop();
switch (c)
{
case '+':
val = op1 + op2;
break;
case '-':
val = op2 - op1;
break;
case '*':
val = op1 * op2;
break;
case '/':
val = op2 / op1;
break;
}
st.push(val);
}
}
return st.top();
}
int _tmain(int argc, _TCHAR* argv[])
{
char inFix[100];
char postFix[100];
double val;
while (1)
{
printf("enter an expression:");
gets_s(inFix);
if (strlen(inFix) == 0)
continue;
printf("\n%s = ", inFix);
inFix2PostFix(inFix, postFix);
printf("%s = ", postFix);
val = postFixEval(postFix);
printf("%.3f\n", val);
}
return 0;
}
轉載請注明本文位址: 中綴表達式轉換成字尾表達式并求值