今天有師妹求助，要實現帶有括號、加減乘除、階乘的表達式計算
一時沖動便給師妹寫了一下，C語言代碼如下，用了兩個棧來實現逆波蘭表達式求值：
[c]
//
#include <stdio.h>
#include <stdlib.h>
//運算符棧的長度
#define OPSTACK_LENGTH 5
//操作數棧的長度
#define NUMSTACK_LENGTH 100
//輸入串的最大長度
#define MAX_STRING_LENGTH 100
//運算符結構體
struct operatorStruct
{
//運算符名稱
char name;
//優先級
int priority;
//目數，即操作數個數，例如單目運算符為1，雙目運算符2
int opnum;
};
typedef struct operatorStruct OPERATOR;
//運算符棧
OPERATOR opStack[OPSTACK_LENGTH];
//運算符棧頂指針
int opStackTop = -1;
//操作數棧
double numStack[NUMSTACK_LENGTH];
//操作數棧頂指針
int numStackTop = -1;
//獲取一個字符所代表的運算符的優先級
int getPriority(char name)
{
if (name == '(' || name == ')')
{
return 0;
}
if (name == '!')
{
return 3;
}
if (name == '*' || name == '/')
{
return 2;
}
if (name == '+' || name == '-')
{
return 1;
}
exit(1);
}
//獲取一個字符所代表的運算符的目數
int getOpNum(char name)
{
if (name == '*' || name == '/' || name == '+' || name == '-')
{
return 2;
}
if (name == '!')
{
return 1;
}
if (name == '(' || name == ')')
{
return 0;
}
exit(1);
}
//運算符壓棧
void pushOperator(OPERATOR op)
{
if (opStackTop < OPSTACK_LENGTH - 1)
{
opStack[++opStackTop] = op;
}
else
{
exit(1);
}
}
//運算符出棧
OPERATOR popOperator()
{
if (opStackTop >= 0)
{
return opStack[opStackTop--];
}
else
{
exit(1);
}
}
//操作數壓棧
void pushNumber(double num)
{
if (numStackTop < NUMSTACK_LENGTH - 1)
{
numStack[++numStackTop] = num;
}
else
{
exit(1);
}
}
//操作數出棧
double popNumber()
{
if (numStackTop >= 0)
{
return numStack[numStackTop--];
}
else
{
exit(1);
}
}
//將輸入字符串中的以0-9開頭、到下一個運算符結束的一段轉化為浮點型
//i加上浮點型對應的字符串的長度
double getNumFromString(char *s, int *i)
{
int j = 0;
static char numstr[MAX_STRING_LENGTH];
while ((*s) >= '0' && *s <= '9')
{
numstr[j++] = (*s);
s++;
}
if ((*s) == '.')
{
numstr[j++] = (*s);
s++;
while ((*s) >= '0' && *s <= '9')
{
numstr[j++] = (*s);
s++;
}
}
(*i) = (*i) + j;
numstr[j] = '\0';
return atof(numstr);
}
//從操作數棧中彈出兩個操作數，完成一次雙目運算
double opertate2Num(OPERATOR op)
{
double num2 = popNumber();
double num1 = popNumber();
if (op.name == '+')
{
return num1 + num2;
}
if (op.name == '-')
{
return num1 - num2;
}
if (op.name == '*')
{
return num1 * num2;
}
if (op.name == '/')
{
return num1 + num2;
}
exit(1);
}
//從操作數棧中彈出一個操作數，完成一次單目運算
double opertate1Num(OPERATOR op)
{
double num = popNumber();
if (op.name == '!')
{
double result = 1;
while (num > 1)
{
result *= num;
num--;
}
return result;
}
exit(1);
}
//完成一次運算 www.2cto.com
double operate(OPERATOR op)
{
if (op.opnum == 1)
{
return opertate1Num(op);
}
else if (op.opnum == 2)
{
return opertate2Num(op);
}
exit(1);
}
int main()
{
char string[MAX_STRING_LENGTH];//表達式的輸入串
int i;
OPERATOR op, topOp;//op為從當前輸入串中提取的一個運算符，topOp為運算符棧棧頂的運算符
topOp.name = '#';
topOp.priority = 0;
topOp.opnum = 0;
pushOperator(topOp);//壓入#作為初始運算符
scanf("%s", string);
for (i = 0; string[i] != '\0' && string[i] != '=';)
{
//從輸入串中取出一個字符作為開始，進行處理，直到表達式結束
if (string[i] >= '0' && string[i] <= '9')
{
//如果是操作數，將整個操作數提取出來，壓入操作數棧
pushNumber(getNumFromString(&string[i], &i));
}
else
{
op.name = string[i];
op.priority = getPriority(string[i]);
op.opnum = getOpNum(string[i]);
topOp = popOperator();
if (op.name == '(')
{
//如果是'('，將從棧頂彈出的運算符壓回棧內，並將當前運算符則壓棧
pushOperator(topOp);
pushOperator(op);
}
else if (op.name == ')')
{
//如果是')'，則進行運算，每次運算結果作為一個操作數壓入操作數棧，直到將'('彈出運算符棧
while (topOp.name != '(')
{
pushNumber(operate(topOp));
topOp = popOperator();
}
}
else
{
//如果是普通運算符
if (topOp.name != '#' && op.priority <= topOp.priority)
{
//如果運算符棧非空，且當前運算符的優先級大於棧頂運算符，則進行一次運算，將結果壓入操作數棧
pushNumber(operate(topOp));
}
else
{
//否則將從棧頂彈出的運算符壓回
pushOperator(topOp);
}
//將當前運算符壓棧
pushOperator(op);
}
i++;
}
}
//完成棧內剩余的運算
while ((topOp = popOperator()).name != '#')
{
pushNumber(operate(topOp));
}
//操作數棧中剩下的最後一個數即為結果
printf("%f\n", popNumber());
return 0;
}
作者：卞昊穹
