mirror of
https://github.com/kangjianwei/Data-Structure.git
synced 2026-02-09 02:02:32 +08:00
140 lines
4.0 KiB
C
140 lines
4.0 KiB
C
/*==============
|
||
* 表达式计算
|
||
*
|
||
* 包含算法: 3.4
|
||
===============*/
|
||
|
||
#include "Expression.h" //**▲03 栈和队列**//
|
||
|
||
/*
|
||
* ████████ 算法3.4 ████████
|
||
*
|
||
* 从exp读入表达式，并计算表达式的运算结果
|
||
*
|
||
*【注】
|
||
* 1.教材使用的是控制台输入，这里为了便于测试，直接改为从形参接收参数
|
||
* 2.该计算功能有限，理论上仅支持对个位数运算，且要求每一步的运算结果也是个位数。
|
||
* 教材提供此算法的目的是验证栈的使用，如果想扩展对运算符的支持，并扩大对操作数的支持，
|
||
* 则可以顺着此思路进行改版
|
||
*/
|
||
OperandType EvaluateExpression(const char exp[]) {
|
||
SElemType c; // 输入序列
|
||
|
||
SqStack OPTR; // 运算符栈
|
||
SqStack OPND; // 操作数栈
|
||
|
||
OperatorType theta, x; // 运算符
|
||
OperandType a, b; // 操作数
|
||
|
||
int i = 0;
|
||
|
||
// 初始化运算符栈，并将一个界限符'#'入栈
|
||
InitStack(&OPTR);
|
||
Push(&OPTR, '#');
|
||
|
||
// 初始化操作数栈，并开始读取输入
|
||
InitStack(&OPND);
|
||
c = exp[i++];
|
||
|
||
// 当输入中遇到界限符'#'，且运算符栈的栈顶元素也是界限符'#'时，则表示读取结束，且运算结束
|
||
while(c != '#' || GetTop(OPTR) != '#') {
|
||
// 如果ch不是运算符，则视其为操作数，将其入栈
|
||
if(!In(c, OP)) {
|
||
Push(&OPND, c); // 将操作数入栈
|
||
c = exp[i++]; // 获取下一个输入字符
|
||
} else {
|
||
switch(Precede(GetTop(OPTR), c)) {
|
||
// 栈中运算符优先级低，继续进栈
|
||
case '<':
|
||
Push(&OPTR, c);
|
||
c = exp[i++];
|
||
break;
|
||
|
||
// 优先级相等时，说明这里遇到括号，需要脱括号
|
||
case '=':
|
||
Pop(&OPTR, &x);
|
||
c = exp[i++];
|
||
break;
|
||
|
||
/*
|
||
* 栈中运算符优先级高时，先计算，再将计算结果压入栈
|
||
*
|
||
* 注：这儿没有读字符，c保留的还是刚才读到的字符
|
||
*/
|
||
case '>':
|
||
Pop(&OPTR, &theta); // 弹出运算符
|
||
Pop(&OPND, &b); // 弹出右边的操作数
|
||
Pop(&OPND, &a); // 弹出左边的操作数
|
||
Push(&OPND, Operate(a, theta, b));
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
|
||
return GetTop(OPND);
|
||
}
|
||
|
||
// 判断指定的运算符是否合规
|
||
Status In(SElemType c, const char OP[]) {
|
||
|
||
SElemType* e = strchr(OP, c);
|
||
|
||
// 如果运算符c不在合规范围内，说明指定的运算符不合规
|
||
if(e == NULL) {
|
||
return FALSE;
|
||
} else {
|
||
return TRUE;
|
||
}
|
||
}
|
||
|
||
/*
|
||
* 判断运算符栈中操作符o1与表达式中的操作符o2的优先级。
|
||
*
|
||
* 返回'>'、'<'、'='，以指示o1和o2的优先级
|
||
*/
|
||
OperatorType Precede(OperatorType o1, OperatorType o2) {
|
||
int x, y;
|
||
|
||
// 获取指定的运算符在运算符表中的位置
|
||
char* p1 = strchr(OP, o1);
|
||
char* p2 = strchr(OP, o2);
|
||
|
||
// 计算出一个运算符优先级表坐标
|
||
x = p1 - OP;
|
||
y = p2 - OP;
|
||
|
||
return PrecedeTable[x][y];
|
||
}
|
||
|
||
/*
|
||
* 对操作数进行运算
|
||
*
|
||
* a、b是操作数，theta是运算符。
|
||
* 对于操作数和运算结果，仅保证对个位数的支持
|
||
*/
|
||
OperandType Operate(OperandType a, OperatorType theta, OperandType b) {
|
||
int x, y, z = CHAR_MAX - 48;
|
||
|
||
// 先从字符型转为整型
|
||
x = a - '0';
|
||
y = b - '0';
|
||
|
||
switch(theta) {
|
||
case '+':
|
||
z = x + y;
|
||
break;
|
||
case '-':
|
||
z = x - y;
|
||
break;
|
||
case '*':
|
||
z = x * y;
|
||
break;
|
||
case '/':
|
||
z = x / y;
|
||
break;
|
||
}
|
||
|
||
// 计算完成后，将整型转换为字符型返回
|
||
return z + 48;
|
||
}
|