內容
後序運算式(postfix)有別於我們習慣的算式寫法(infix)，是把運算子寫在運算元之後，雖然對人來說可讀性很低，可是對電腦來說卻是很方便的運算式子。運算式用後序表示法的好處還有不用去考慮中序式的先乘除後加減的問題以及免除所有的括號。
比如我們習慣 3 + 5 這樣的式子，就是中序運算式
同一個式子改成後序寫法即為 3 5 +
現在給你一個後序運算式，請求出這個式子的結果。
輸入
輸入一個後序運算式的字串包含數個運算子及運算元，為了方便讀取，所有的運算元與運算子之間都以空格隔開。
運算子包含 + - * / % 等五個
運算元則為 0 ~231 -1 的整數
3 5 +
6 3 / 1 4 - * 3 + 8 -
輸出
輸出該後序運算式的結果。
為避免小數誤差問題，運算結果必定為整數，運算過程中也必定不會出現小數的結果，因此請放心使用整數來進行運算
8
-11
解題思路
後序轉中序輸出。
完整程式碼
AC (2ms, 100KB)
#include <stdio.h>
#define MAX 10000
long long stack[MAX];
int sTop;
char postfix[MAX];
long long cale(long long lhs, long long rhs, char op)
{
switch (op)
{
case '+': return lhs + rhs;
case '-': return lhs - rhs;
case '*': return lhs * rhs;
case '/': return lhs / rhs;
case '%': return lhs % rhs;
}
return -1;
}
long long postfixToInt(char* postfix)
{
stack[0] = sTop = 0;
char* now = postfix - 1;
for (int i = 0; postfix[i]; i++)
{
if (postfix[i] >= '0' && postfix[i] <= '9')
stack[sTop] = (stack[sTop] << 3) + (stack[sTop] << 1) + (postfix[i] - '0');
else if (postfix[i] == ' ')
sTop++;
else
{
sTop -= 2;
stack[sTop] = cale(stack[sTop], stack[sTop + 1], postfix[i]);
stack[sTop + 1] = 0;
}
}
return stack[0];
}
int main()
{
while (gets(postfix) != NULL)
{
printf("%lld\n", postfixToInt(postfix));
}
return 0;
}
|
