首页 > 编程语言 >【数据结构】例题：表达式求值 C++实现

【数据结构】例题：表达式求值 C++实现

时间：2022-11-08 21:46:35浏览次数：48  
标签：算符 return 栈顶 C++ 运算符 求值 例题 Stack 表达式

先写一个链栈

#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所示。

【思路】利用栈后进先出的特性，优先级低的运算符先入栈，优先级高的运算符后入栈。因此越往栈底优先级越低，越靠近栈顶优先级越高

过程：

  • 初始化一个算符栈，自左向右扫描表达式
  • 当扫描到的是操作数时直接输出，继续处理下一个字符；
  • 若优先级：栈顶算符 < 读取的算符，则入栈，继续处理下一个字符；
  • 若优先级：栈顶算符 > 读取的算符，则从算符栈出栈一个运算符输出，仍然处理当前字符；
  • 若优先级：栈顶算符 = 读取的算符，则为括号（也有可能是 #），括号从算符栈中出栈不保存，继续处理下一个字符。
  • 结束条件是算符栈已空，最后在转换的字符末尾加上 # 和 \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]{'+', '-', '*', '/', '(', ')', '#'};
  • 定义二维静态数组表示优先关系
static char PriorityTab[7][7]
{	
	{'>', '>', '<', '<', '<', '>', '>'},
	{'>', '>', '<', '<', '<', '>', '>'},
	{'>', '>', '>', '>', '<', '>', '>'},
	{'>', '>', '>', '>', '<', '>', '>'},
	{'<', '<', '<', '<', '<', '=', '/'},
	{'>', '>', '>', '>', '/', '>', '>'},
	{'<', '<', '<', '<', '<', '/', '='} 
};

/// 运算符优先级比较
/// @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

相关文章

  • C++面经 ----- C++11新特性：左值右值
    概念左值：可以取地址并且有名字的东西就是左值。右值：不能取地址的没有名字的东西就是右值。纯右值：运算表达式产生的临时变量、不和对象关联的原始字面量、非引用返回......
  • C++ 面经 ----- C++11新特性：auto & decltype 类型推导
    C++11引入了auto和decltype关键字使用他们可以在编译期就推导出变量或者表达式的类型，方便开发者编码也简化了代码。 auto示例autoa=10;//10是int型，可以自动推导......
  • 使用一条for语句求若干个整数的平均值--C++自学
    #include<iostream>#include<stdlib.h>usingnamespacestd;intmain(){intx,count=0,sum=0;cout<<"输入若干整数："<<endl;cin>>x;for(;x!=......
  • 问题 I: 零基础学C/C++172——猴子选大王
    提示中也说了，这题可以用循环列表来实现，但是其实我也不怎么会哈哈哈哈，这题也同样可以用简单的基础语法来实现，只不过我们需要对一个循环语句做些手脚，让他头尾相连。点击查......
  • 问题 F: 零基础学C/C++176——生日相同问题
    首先题目也很明确的要求了按照日期从前到后，若日期相同，则比的是名字从短到长顺序输出，长度相同的按字典序输出。如果没有生日相同的学生，输出None。所以这题的一大难点也就......
  • 问题 N: 零基础学C/C++159——最长字符串
    题目一点也不难哦，就是要学会二维数组的输入输出但是不知为何这题有一个很奇怪的坑，如果你是AC:83%那么恭喜你掉坑里了!!这道题目竟然有一个检测点在最后的时候加\n确实......
  • 问题 M: 零基础学C/C++158——删除中间的*
    思路很简单，但实现起来有点麻烦。将前面2题融合（前两题我就觉得没必要放了哈哈哈哈），保留前面与后面的*都改成删除即可。你会发现我的代码是前两个的融合。要学会融会贯通鸭:......
  • C++ 何时需要使用 引用 & ?
    原因：在C++中,由于以下原因,变量通过引用传递：1)要修改调用者函数的局部变量：引用(或指针)允许被调用函数修改调用者函数的局部变量。例如,考虑以下示例程序,其......
  • C++ 关于size()和sizeof()的区别
    sizeof（a）返回的是对象占用内存的字节数，而a.size()是string类定义的一个返回字符串大小的函数，两个是完全不一样的概念。明确两者的概念和作用：1、size()函数：c++中，在获取字......
  • 《数据结构与算法分析（C++语言描述）》
    在看这本书总结了笔记，并分享出来。有问题请及时联系博主：​​Alliswell_WP​​，转载请注明出处。书籍：《数据结构与算法分析（C++语言描述）》作者：LarryNyhoff著、黄达明等译源代......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99