先写一个链栈
#pragma once
/// 链栈的结点类型
template<class DataType>
class StackNode
{
public:
DataType data;
StackNode* next;
StackNode() {
next = nullptr;
}
};
/// 链栈类
template<class DataType>
class LinkStack
{
private:
StackNode<DataType>* top;
public:
/// 构造函数.
/// 构造一个空栈.
LinkStack() {
top = nullptr;
}
/// 析构函数
/// 销毁一个已存在的栈
~LinkStack()
{
StackNode<DataType>* p;
while (top)// 销毁栈中的所有元素
{
p = top;
top = top->next;
delete p;
}
top = nullptr;// 栈顶指针赋值为空,表示空栈
}
/// 判断栈是否为空.
/// @return 为空返回 true,否则返回 false
bool Empty_Stack();
/// 将元素插入栈顶
/// @param e 要压入栈顶的值
/// @return 压栈操作失败返回 false,否则返回 true.
bool Push_Stack(DataType e);
/// 从栈顶删除一个元素到 e 中返回
/// @param e 用于返回的变量
/// @return 如栈为空,则出栈操作失败返回 false,否则返回 true.
bool Pop_Stack(DataType& e);
/// 从栈顶取出一个元素到 e 中返回.
/// 取栈顶元素是获取出栈顶元素的值,而不改变栈.
/// @param e 用于返回的变量
/// @return 如栈为空,则取栈顶元素操作失败返回 false,否则返回 true
bool GetTop_Stack(DataType& e);
};
template<class DataType>
inline bool LinkStack<DataType>::Empty_Stack()
{
return (!top);
}
template<class DataType>
inline bool LinkStack<DataType>::Push_Stack(DataType e)
{
StackNode<DataType>* node = new StackNode<DataType>;// 申请结点
if (node)// 如果结点申请成功
{
node->data = e;
node->next = top;
top = node;// 修改栈顶指针
return true;
}
else
{
return false;
}
}
template<class DataType>
inline bool LinkStack<DataType>::Pop_Stack(DataType& e)
{
StackNode<DataType>* p;
if (top)
{
e = top->data;
p = top;
top = top->next;// 修改栈顶指针
delete p;// 删除结点
return true;
}
else
{
return false;
}
}
template<class DataType>
inline bool LinkStack<DataType>::GetTop_Stack(DataType& e)
{
if (top)
{
e = top->data;
return true;
}
else
{
return false;
}
}
【例4.3】表达式求值
任何一个表达式都是由操作数、运算符和界限符组成的有意义的式子。
- 操作数既可以是常数,也可以是变量或常量。
- 运算符从运算对象的个数来分,有单目运算符、双目运算符和三目运算符;从运算类型来分,有算术运算、关系运算、逻辑运算。
- 界限符有左右括号和表达式结束符等。运算符、界限符统称算符。
为简单化,这里仅限于讨论只含双目运算符的加、减、乘、除算术表达式,并且操作数为一位字符表示的整数。并且约定,表达式以 #
为结束字符
在表达式求值时,一般表达式有以下 3 种表示形式。
① 后缀表示:<操作数><操作数><运算符>
;
② 中缀表示:<操作数><运算符><操作数>
;
③ 前缀表示:<运算符><操作数><操作数>
;
由于中缀表示中有算符的优先级问题,有时还采用括号改变运算顺序,因此一般在表达式求值中,较少采用中缀表示,在编译系统中更常见的是采用后缀表示。
(1)后缀表达式(也称逆波兰式)求值。
-
由于后缀表达式的操作数总在运算符之前,并且表达式中既无括号又无优先级的约束,算法比较简单。
-
具体做法:只使用一个操作数栈,当从左向右扫描表达式:
- 每遇到一个操作数就送入栈中保存
- 每遇到一个运算符就从栈中取出两个操作数进行当前的计算,然后把结果再入栈
- 结束条件为整个表达式结束,这时送入栈顶的值就是结果。
/// 判断一个字符是否是数字
/// @return 如果是数字,返回 true,否则返回 false
bool IsNum(const char& ch)
{
if (ch >= '0' && ch <= '9')
{
return true;
}
else
{
return false;
}
}
/// 逆波兰表达式求值
/// @param A 表达式字符串
/// @return 返回计算结果,表达式不合法返回 NAN
double RPN_Arithmetic(char* A)
{
LinkStack<double> S;
double result, a, b, c;
char ch;
ch = *A++;
while (ch != '#')
{
if (IsNum(ch))
{
// 每遇到一个操作数就送入栈中保存
S.Push_Stack(ch - '0');
}
else
{
// 每遇到一个运算符就从栈中取出两个操作数进行当前的计算
S.Pop_Stack(b);
S.Pop_Stack(a);
switch (ch)
{
case '+':
c = a + b;
break;
case '-':
c = a - b;
break;
case '*':
c = a * b;
break;
case '/':
c = a / b;
break;
default:
// 运算符不合法
return NAN;
break;
}
// 计算结果再入栈
S.Push_Stack(c);
}
ch = *A++;
}
// 出栈输出计算结果
S.Pop_Stack(result);
return result;
}
(2)中缀表达式转换为后缀表达式
根据中缀表达式中算术运算规则,式子 <操作数>θ1<操作数>θ2<操作数>
中,θ1、θ2的运算优先关系如图4.8所示。
![](/i/l/?n=22&i=blog/2641204/202211/2641204-20221108213026258-765655586.png)
【思路】利用栈后进先出的特性,优先级低的运算符先入栈,优先级高的运算符后入栈。因此越往栈底优先级越低,越靠近栈顶优先级越高
过程:
- 初始化一个算符栈,自左向右扫描表达式
- 当扫描到的是操作数时直接输出,继续处理下一个字符;
- 若优先级:
栈顶算符 < 读取的算符
,则入栈,继续处理下一个字符; - 若优先级:
栈顶算符 > 读取的算符
,则从算符栈出栈一个运算符输出,仍然处理当前字符; - 若优先级:
栈顶算符 = 读取的算符
,则为括号(也有可能是#
),括号从算符栈中出栈不保存,继续处理下一个字符。 - 结束条件是算符栈已空,最后在转换的字符末尾加上
#
和\0
,转换成功,结束。
例如:(2+3)*(1+2)#
算符栈 | 比较 | 输出 |
---|---|---|
# |
# < ( |
|
#( |
2 | |
#( |
( < + |
2 |
#(+ |
23 | |
#(+ |
+ > ) |
23+ |
#( |
( = ) |
23+ |
# |
# < * |
23+ |
#* |
* < ( |
23+ |
#*( |
23+1 | |
#*( |
( < + |
23+1 |
#*(+ |
23+12 | |
#*(+ |
+ > ) |
23+12+ |
#*( |
( = ) |
23+12+ |
#* |
* > # |
23+12+* |
# |
# = # |
23+12+* |
Empty_Stack() = true |
23+12+*# |
然后末尾加上 #
和 \0
就转换成功。
比较算符优先级的算法:
- 定义一维数组映射字符
static char OP[7]{'+', '-', '*', '/', '(', ')', '#'};
![](/i/l/?n=22&i=blog/2641204/202211/2641204-20221108213234167-663733475.png)
- 定义二维静态数组表示优先关系
static char PriorityTab[7][7]
{
{'>', '>', '<', '<', '<', '>', '>'},
{'>', '>', '<', '<', '<', '>', '>'},
{'>', '>', '>', '>', '<', '>', '>'},
{'>', '>', '>', '>', '<', '>', '>'},
{'<', '<', '<', '<', '<', '=', '/'},
{'>', '>', '>', '>', '/', '>', '>'},
{'<', '<', '<', '<', '<', '/', '='}
};
![](/i/l/?n=22&i=blog/2641204/202211/2641204-20221108213346639-356894168.png)
/// 运算符优先级比较
/// @param theta1 第一个运算符
/// @param theta2 第二个运算符
/// @return 比较结果,theta1 < theta2 返回 '<',theta1 = theta2 返回 '=',<br>
/// theta1 > theta2 返回 '>',语法错误返回 '/'
char OperatorComp(const char& theta1, const char& theta2)
{
int i, row, col;
// 定义一维数组映射字符
static char OP[7]{'+', '-', '*', '/', '(', ')', '#'};
// 定义二维静态数组表示优先关系
static char PriorityTab[7][7]
{
{'>', '>', '<', '<', '<', '>', '>'},
{'>', '>', '<', '<', '<', '>', '>'},
{'>', '>', '>', '>', '<', '>', '>'},
{'>', '>', '>', '>', '<', '>', '>'},
{'<', '<', '<', '<', '<', '=', '/'},
{'>', '>', '>', '>', '/', '>', '>'},
{'<', '<', '<', '<', '<', '/', '='}
};
// 求出theta1的字符映射下标
for (i = 0; i < 7; i++)
{
if (OP[i] == theta1)
{
row = i;
break;
}
}
// 求出theta2的字符映射下标
for (i = 0; i < 7; i++)
{
if (OP[i] == theta2)
{
col = i;
break;
}
}
if (row < 7 && col < 7)
{
return PriorityTab[row][col];
}
else
return '/';// theta1或者theta2非法运算符
}
中缀表达式转换为后缀表达式算法
/// 中缀表达式转换为逆波兰表达式
/// @param infixexp 中缀表达式字符串
/// @param RPN 转换结果输出
/// @return 转换成功返回 true,表达式不合法,转换失败返回 false
bool Infix2RPN(char* infixexp, char* RPN)
{
LinkStack<char> S;
S.Push_Stack('#');
char ch = *infixexp++;
char ch0;
while (!S.Empty_Stack())
{
if (IsNum(ch))
{
// 碰到数组直接输出
*RPN = ch;
RPN++;
ch = *infixexp++;// 处理下一个字符
}
else // 不是数字就是运算符
{
S.GetTop_Stack(ch0);// 取栈顶运算符
switch (OperatorComp(ch0, ch))// 比较栈顶运算符与读取的运算符的优先级
{
case '<':
// 栈顶运算符 < 读取的运算符
// 读取的运算符入栈,处理下一个字符
S.Push_Stack(ch);
ch = *infixexp++;
break;
case '>':
// 栈顶运算符 > 读取的运算符
// 栈顶运算符出栈输出,继续处理当前字符
S.Pop_Stack(ch0);
*RPN = ch0;
RPN++;
break;
case '=':
// 栈顶运算符 = 读取的运算符
// 出栈,括号出栈不保存,处理下一个字符
S.Pop_Stack(ch0);
ch = *infixexp++;
break;
default:
// 中缀表达式不合法
return false;
}
}
}
// 结束字符
*RPN = '#';
RPN++;
*RPN = '\0';
return true;
}
(6)中缀表达式求值
中缀表达式求值方法有两种:
- 一种是先转换为后缀表达式,再求值。
- 第二种是用一个算符栈和一个操作数栈,从头开始扫描表达式:
- 若读取到数字,直接压入操作数栈,继续处理下一个字符;
- 若读取到运算符,比较栈顶算符与读取的算符的优先级:
栈顶算符 < 读取的算符
将读取的算符压入栈,继续处理下一个字符;栈顶算符 > 读取的算符
栈顶算符出栈,从操作数栈中取出两数字,根据出栈算符做运算,运算结果再压入操作数栈,继续处理当前字符;栈顶算符 = 读取的算符
栈顶算符出栈,括号出栈不保存,继续处理下一个字符;
- 结束条件是算符栈已空,最后操作数栈出栈输出计算结果。
第二种方法:
/// 中缀表达式求值
/// @param infixexp 中缀表达式字符串
/// @return 返回计算结果,表达式不合法返回 NAN
double Infix_Arithmetic(char* infixexp)
{
LinkStack<char> operatorStack;// 算符栈
operatorStack.Push_Stack('#');
LinkStack<double> numberStack;// 操作数栈
char w = *infixexp++, ch0;
double result, a, b, c;
while (!operatorStack.Empty_Stack())
{
if (IsNum(w))// 如为数字
{
// 存入操作数栈
numberStack.Push_Stack(w - '0');
w = *infixexp++;
}
else
{
// 取算符栈栈顶算符
operatorStack.GetTop_Stack(ch0);
switch (OperatorComp(ch0, w))// 比较栈顶算符与读取的算符的优先级
{
case '<':// 栈顶算符 < 读取的算符
// 读取的算符压入算符栈,处理下一个字符
operatorStack.Push_Stack(w);
w = *infixexp++;
break;
case '>':// 栈顶算符 > 读取的算符
// 栈顶算符出栈
operatorStack.Pop_Stack(ch0);
// 从操作数栈取两个元素,来进行计算
numberStack.Pop_Stack(b);
numberStack.Pop_Stack(a);
switch (ch0)
{
case '+':
c = a + b;
break;
case '-':
c = a - b;
break;
case '*':
c = a * b;
break;
case '/':
c = a / b;
break;
default:
return NAN;
}
// 计算并将计算结果压入操作数栈,继续处理当前字符
numberStack.Push_Stack(c);
break;
case '=':// 栈顶算符 = 读取的算符
// 括号出栈但不保存
operatorStack.Pop_Stack(ch0);
// 处理下一个字符
w = *infixexp++;
break;
default:
return NAN;
break;
}
}
}
numberStack.Pop_Stack(result);
return result;
}
标签:算符,return,栈顶,C++,运算符,求值,例题,Stack,表达式
From: https://www.cnblogs.com/Critical-Thinking/p/16871310.html