精华内容
下载资源
问答
  • 表达式求值

    千次阅读 2018-07-13 18:38:54
    这里对严蔚敏版的数据结构一书中表达式求值算法给出代码实现.具体参见严蔚敏版数据结构表达式取值章节.表达式求值 实际使用栈来做, 也就是说 , 表达式求值实际是栈的应用 . 这里采用 " 算符 优先法" 对...

    这里对严蔚敏版的数据结构一书中表达式求值算法给出代码实现.

    具体参见严蔚敏版数据结构表达式取值章节.

    表达式求值 实际使用栈来做, 也就是说 , 表达式求值实际是栈的应用 . 这里采用 " 算符 优先法" 对表达式求值.代码里实现的是基于加减乘除的整数运算 . 没有对表达式出错情况进行处理. 如果读者需要出错处理 , 在Precede()函数里返回0的代表表达式出错 . 读者可依据返回值自行处理 .

    本算法使用两个工作栈 , SqStack_OPTR工作栈 , 用来存放运算符 . SqStack_OPND工作栈 , 用来存放操作数或运算结果 . 因为一个表达式根本上就是由运算符和操作数组成 , 所以这里用到了两个工作栈.

    表达式以#开始 , 以#结束 . 开始的#不由用户输入 , 代码 里在创建栈是自动加入 . 结束的#号用户手动输入 , 用来表示一个表达式的结束 .

    具体的算法思路不在这里解释了 ,写了一下午了, 脖子有点疼 .

    给出算符优先级表 , Precede()函数依据算符优先级表来确定两个操作数的关系 .

    算符优先关系表
     +-*/()#
    +>><<<>>
    ->><<<>>
    *>>>><>>
    />>>><>>
    (<<<<<=0
    )>>>>0>>
    #<<<<<0=

    具体代码如下:

    #include<iostream>
    #include<stdlib.h>
    #define STACK_INIT_SIZE 100  //存储空间初始分配量 
    #define STACKINCREMENT 10  //存储空间增量
    using namespace std;
    typedef  struct
    {
    	int *base;  //栈底指针 ,构造前和销毁后都为NULL
    	int *top;  //栈顶指针
    	int stacksize ; //当前以分配的存储空间 
     } SqStack_OPND;
     
     
    typedef  struct
    {
    	char *base;  //栈底指针 ,构造前和销毁后都为NULL
    	char *top;  //栈顶指针
    	int stacksize ; //当前以分配的存储空间 
     } SqStack_OPTR;
     
     
    bool   InitStack_OPND(SqStack_OPND &s)
    {
    	//构造一个空栈
    	s.base = (int*) malloc(STACK_INIT_SIZE * sizeof(int) ) ;
    	if(!s.base)  return false;
    	s.top = s.base;
    	s.stacksize = STACK_INIT_SIZE;
    	return true;
    } 
    
    bool   InitStack_OPTR(SqStack_OPTR &s)
    {
    	//构造一个空栈
    	s.base = (char*) malloc(STACK_INIT_SIZE * sizeof(char) ) ;
    	if(!s.base)  return false;
    	s.top = s.base;
    	s.stacksize = STACK_INIT_SIZE;
    	return true;
    } 
    
    
    char  GetTop_OPTR(SqStack_OPTR &s )
    {
    	//若栈不为空,返回字符e ,否则返回数值0 
    	char e;
    	if(s.top == s.base)  return 0;
    	e = *(s.top-1);
    	return e;
    }
    
    
    char  GetTop_OPND(SqStack_OPND &s )
    {
    	//若栈不为空,返回字符e ,否则返回数值0 
    	int e;
    	if(s.top == s.base)  return 0;
    	e = *(s.top-1);
    	return e;
    }
    
    
    bool  Push_OPTR(SqStack_OPTR &s  , char e)
    {
    	//插入e为新的栈顶元素
    	if(s.top - s.base > s.stacksize)	{   //栈满,追加存储空间 
    		s.base = (char*) realloc(s.base  , (s.stacksize + STACKINCREMENT)  * sizeof(char) );
    		if(!s.base) return false;
    		s.top =  s.base + s.stacksize;
    		s.stacksize += STACKINCREMENT;
    	 } //增加空间完毕 
    	 
    	 *s.top++ = e;
    	 return true;
    }
    
    
    bool  Push_OPND(SqStack_OPND &s  , int e)
    {
    	//插入e为新的栈顶元素
    	if(s.top - s.base > s.stacksize)	{   //栈满,追加存储空间 
    		s.base = (int*) realloc(s.base  , (s.stacksize + STACKINCREMENT)  * sizeof(int) );
    		if(!s.base) return false;
    		s.top =  s.base + s.stacksize;
    		s.stacksize += STACKINCREMENT;
    	 } //增加空间完毕 
    	 
    	 *s.top++ = e;
    	 return true;
    }
    
    
    bool Pop_OPTR(SqStack_OPTR &s , char &e)
    {
    	//若栈不为空,删除s的栈顶元素,用e返回其值,并返回true , 否则返回false
    	if(s.top == s.base)  return false;
    	e = * --s.top;
    	return  true; 
    }
    
    
    bool Pop_OPND(SqStack_OPND &s , int &e)
    {
    	//若栈不为空,删除s的栈顶元素,用e返回其值,并返回true , 否则返回false
    	if(s.top == s.base)  return false;
    	e = * --s.top;
    	return  true; 
    }
    
    
    //定义两个工作栈
    //用来寄存运算符的栈   :  OPTR
    //用来寄存操作数或运算结果的栈   :  OPND
    SqStack_OPTR OPTR ;
    SqStack_OPND OPND ;
    
    int e;  //接收栈顶元素 GetTop() 和 Pop()中用到
    
    char Precede(char  e , char c)  //根据算符优先关系表,返回三个优先关系之一 
    {
    		//规定, e 为01 ,c 为 02
    		int convert_e , convert_c; //将e 和 c 转换为数字在进行比较,方便代码书写和理解
    		
    		//对e 进行转换 
    		switch(e)
    		{
    			case '+' : convert_e = 1 ;  break;
    			case '-' : convert_e = 2 ;  break;	
    			case '*' : convert_e = 3 ;  break;
    			case '/' : convert_e = 4 ;  break;
    			case '(' : convert_e = 5 ;  break;
    			case ')' : convert_e = 6 ;  break;
    			case '#' : convert_e = 7 ;  break;
    		} 
    		
    		
    		//对c 进行转换 
    		switch(c)
    		{
    			case '+' : convert_c = 1 ;  break;
    			case '-' : convert_c = 2 ;  break;	
    			case '*' : convert_c = 3 ;  break;
    			case '/' : convert_c = 4 ;  break;
    			case '(' : convert_c = 5 ;  break;
    			case ')' : convert_c = 6 ;  break;
    			case '#' : convert_c = 7 ;  break;
    		} 
    		
    		if(convert_e == 1 && convert_c == 1)  return '>';
    		if(convert_e == 1 && convert_c == 2)  return '>';
    		if(convert_e == 1 && convert_c == 3)  return '<';
    		if(convert_e == 1 && convert_c == 4)  return '<';
    		if(convert_e == 1 && convert_c == 5)  return '<';
    		if(convert_e == 1 && convert_c == 6)  return '>';
    		if(convert_e == 1 && convert_c == 7)  return '>';
    		
    		
    		
    		if(convert_e == 2 && convert_c == 1)  return '>';
    		if(convert_e == 2 && convert_c == 2)  return '>';
    		if(convert_e == 2 && convert_c == 3)  return '<';
    		if(convert_e == 2 && convert_c == 4)  return '<';
    		if(convert_e == 2 && convert_c == 5)  return '<';
    		if(convert_e == 2 && convert_c == 6)  return '>';
    		if(convert_e == 2 && convert_c == 7)  return '>';
    		
    		
    		if(convert_e == 3 && convert_c == 1)  return '>';
    		if(convert_e == 3 && convert_c == 2)  return '>';
    		if(convert_e == 3 && convert_c == 3)  return '>';
    		if(convert_e == 3 && convert_c == 4)  return '>';
    		if(convert_e == 3 && convert_c == 5)  return '<';
    		if(convert_e == 3 && convert_c == 6)  return '>';
    		if(convert_e == 3 && convert_c == 7)  return '>';
    		
    		
    		
    		if(convert_e == 4 && convert_c == 1)  return '>';
    		if(convert_e == 4 && convert_c == 2)  return '>';
    		if(convert_e == 4 && convert_c == 3)  return '>';
    		if(convert_e == 4 && convert_c == 4)  return '>';
    		if(convert_e == 4 && convert_c == 5)  return '<';
    		if(convert_e == 4 && convert_c == 6)  return '>';
    		if(convert_e == 4 && convert_c == 7)  return '>';
    		
    		
    		if(convert_e == 5 && convert_c == 1)  return '<';
    		if(convert_e == 5 && convert_c == 2)  return '<';
    		if(convert_e == 5 && convert_c == 3)  return '<';
    		if(convert_e == 5 && convert_c == 4)  return '<';
    		if(convert_e == 5 && convert_c == 5)  return '<';
    		if(convert_e == 5 && convert_c == 6)  return '=';
    		if(convert_e == 5 && convert_c == 7)  return '0';  //出现语法错误是返回字符0  因为 (  和 # 不允许相继出现 
    		
    		
    		if(convert_e == 6 && convert_c == 1)  return '>';
    		if(convert_e == 6 && convert_c == 2)  return '>';
    		if(convert_e == 6 && convert_c == 3)  return '>';
    		if(convert_e == 6 && convert_c == 4)  return '>';
    		if(convert_e == 6 && convert_c == 5)  return '0';   // 不允许出现 ) ( 的形式 
    		if(convert_e == 6 && convert_c == 6)  return '>';
    		if(convert_e == 6 && convert_c == 7)  return '>'; 
    		
    		
    		if(convert_e == 7 && convert_c == 1)  return '<';
    		if(convert_e == 7 && convert_c == 2)  return '<';
    		if(convert_e == 7 && convert_c == 3)  return '<';
    		if(convert_e == 7 && convert_c == 4)  return '<';
    		if(convert_e == 7 && convert_c == 5)  return '<';
    		if(convert_e == 7 && convert_c == 6)  return '0';  //# 和 ( 不允许同时相继出现 
    		if(convert_e == 7 && convert_c == 7)  return '=';
    } //Precede
    
    char theta;  // 在Precede()函数判出> 的情况下, 存放从OPTR中出栈的运算符
    
    //返回运算结果  theta为操作数  a 和 b 为运算符左值 和 右值 
    int  Operate(int a , char theta , int b)
    {
    	switch(theta)
    	{
    		case '+' : return a+b;
    		case '-' : return a-b;
    		case '*' : return a*b;
    		case '/' : return a/b;
    	}
    } 
    
    bool In(char c)
    {
    	switch(c)
    	{
    		case '+' :
    		case '-' :
    		case '*' :
    		case '/' :
    		case '(' :
    		case ')' :
    		case '#' : return true;
    	}
    	return false;
    }
    
    
    
    int  EvaluateExpression()   //int 是返回表达式运算后的最终结果 
    {
    	char c;
    	InitStack_OPTR(OPTR);   Push_OPTR(OPTR , '#');
    	InitStack_OPND(OPND);   c = getchar();
    	
    	while( c != '#' || GetTop_OPTR(OPTR) != '#')
    	{
    		if(!In(c)) 
    		{
    			
    			Push_OPND(OPND , c-48); c =getchar();  //不是运算符则进栈 
    		}
    		else
    		{
    			switch( Precede(GetTop_OPTR(OPTR) , c) )
    			{
    				case '<':  //栈顶元素优先权低
    				{
    					Push_OPTR(OPTR , c) ; c = getchar(); break;
    				} 
    				
    				case '=':  //脱括号并接收下一个字符
    				{
    					char x; //接收退栈后的值 
    					Pop_OPTR(OPTR , x) ;  c = getchar(); break;
    				} 
    				
    				case '>':  //退栈并将结果存入栈
    				{
    					int a ,b;
    					Pop_OPTR(OPTR , theta);
    					Pop_OPND(OPND , b); Pop_OPND(OPND ,a);
    					Push_OPND(OPND , Operate(a ,theta ,b));
    					break;
    				} 
    			}//switch
    		}
    	} //while
    	return GetTop_OPND(OPND);
    } 
    
    int main()
    {
    	cout<<"输入表达式,得出运算结果,输入以#结束,输入完毕请按回车!"<<endl;
    	int result = EvaluateExpression();
    	cout<<"表达式结果为:"<<endl;
    	cout<<result<<endl;
    	return 0;
    }

    运行结果图:


    展开全文
  • 表达式求值前缀表达式题目:方法一 :非常巧妙方法2:采用递归后缀表达式中缀表达式思路 前缀表达式 题目: 求前缀表达式的值 (25point(s)) 算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指...

    前缀表达式

    题目:

    求前缀表达式的值 (25point(s))
    算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前,例如2+3*(7-4)+8/4的前缀表达式是:+ + 2 * 3 - 7 4 / 8 4。请设计程序计算前缀表达式的结果值。

    输入格式:
    输入在一行内给出不超过30个字符的前缀表达式,只包含+、-、*、/以及运算数,不同对象(运算数、运算符号)之间以空格分隔。

    输出格式:
    输出前缀表达式的运算结果,保留小数点后1位,或错误信息ERROR。

    输入样例:

    +  + 2 * 3 - 7 4 / 8 4
    

    输出样例:

    13.0
    

    方法一 :非常巧妙

    前缀表达式咋看上去与后缀表达式不一样,没办法用栈处理直接求值,其实是可以的。我只要改变下表达式的扫描方式,从右往左扫描,就变成了了后缀表达式

    从左往右扫描:

    • 如果是数字,转换为数字入栈;
    • 如果是字符,弹出栈顶两数运算,计算结果入栈
    • 直到序列扫描完毕,如果栈正好剩下一个元素,就是最终计算结果

    是不是非常巧妙!
    代码如下:

    //方法1
    //使用字符串流stringstream对double和string进行相互转换
    //也可以用string的全局函数:double->string,使用std::to_string, string→double使用std::stod
    //前缀运算符,从后往前将数字压入stack,遇到操作符则弹出两个数字进行运算
    //把输入的每个数当成浮点型运算,每次读入一个单词到string,使用vector保存
    #include<iostream>
    #include<stack>
    #include<vector>
    #include<string>
    #include<iomanip>
    using std::cin;
    using std::cout;
    using std::endl;
    using std::stod;
    
    bool isOp(std::string s) {
    	if (s == "+" || s == "-" || s == "*" || s == "/")
    		return true;
    	else
    		return false;
    }
    int main() {
    	std::string str;
    	std::vector<std::string> vec;
    	while (cin.peek() != '\n') {
    		cin >> str;
    		vec.push_back(str);
    	}
    	int n = vec.size();
    	std::stack<double> sstack;
    	double a = 0, b = 0;			//我写成int a,b了
    	for (int i = n - 1; i >= 0; i--) { //从右往左扫描,如果是数字,转换为数字入栈;如果是字符,栈顶弹出两数运算,结果入栈
    		if (!isOp(vec[i]))
    			sstack.push(stod(vec[i]));	//如果是数字,直接入栈
    		else {							//如果是符号,弹出两个数参与运算,且把结果入栈
    			if (sstack.size() < 2) {
    				cout << "ERROR" << endl;
    				break;				//return 0;也行
    			}
    			a = sstack.top();
    			sstack.pop();
    			b = sstack.top();
    			sstack.pop();
    			//switch (vec[i])			//条件表达式必须是整型或者枚举类型, 字符串类型是不行的
    			switch (vec[i][0]) {		//所以用字符类型
    			case '+':
    				sstack.push(a + b); break;
    			case '-':
    				sstack.push(a - b); break;
    			case '*':
    					sstack.push(a * b); break;
    			case '/':					//忘了除数可能为0
    				if (b == 0) {
    					cout << "ERROR" << endl;
    					return 0;
    				}
    				sstack.push(a / b); break;
    			default:
    				cout << "ERROR" << endl;
    				break;
    			}
    		}
    	}
    	//最后扫描完了,栈中应该只剩一个数,就是结果
    	if (sstack.size() == 1)
    		cout << std::fixed <<std::setprecision(1) << sstack.top() << endl;
    	else 
    		cout << "ERROR" << endl;
    	return 0;
    }
    

    方法2:采用递归

    后缀表达式

    后缀表达式的求值,跟前缀表达式求值方法1一模一样,它从左往右扫描

    • 如果碰到的数字,入栈
    • 如果碰到的是运算符,弹出栈顶两数参与运算,计算结果入栈

    中缀表达式

    我先将中缀表达式转换为后缀表达式。
    习题3.11 表达式转换 (25point(s))
    算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

    输入格式:
    输入在一行中给出不含空格的中缀表达式,可包含+、-、*、\以及左右括号(),表达式不超过20个字符。

    输出格式:
    在一行中输出转换后的后缀表达式,要求不同对象(运算数、运算符号)之间以空格分隔,但结尾不得有多余空格。

    输入样例:

    2+3*(7-4)+8/4
    

    输出样例:

    2 3 7 4 - * + 8 4 / +
    

    思路

    用map<char,int>来比较优先级,思维导图如下:对于碰到的序列字符a[i]

    在这里插入图片描述

    //用map<char,int>来比较优先级
    #include<iostream>
    #include<string>
    #include<stack>
    #include<map>
    using namespace std;
    
    int main() {
    	string str;
    	stack<char> s;
    	cin >> str;			//因为表达式中间无空格,读入了整个表达式
    	//优先级
    	map<char, int>p;
    	p['+'] = p['-'] = 0;
    	p['*'] = p['/'] = 1;
    	p['('] = p[')'] = 2;
    
    	int flag = 0;//用来控制队首不输出空格
    	for (int i = 0; i < str.length(); i++) {
    		//str[i]两种情况,一种是数字或正负号, 一种是符号
    		if (((i == 0 || str[i - 1] == '(') && (str[i] == '+' || str[i] == '-')) || (str[i] >= '0' && str[i] <= '9')) {
    			if (flag)//flag==0时,就不输出空格了
    				cout << " ";
    			flag = 1;
    			if (str[i] != '+')cout << str[i];//a[i]是正号就不用输出了,必须有这句,不然报错了
    			while (str[i + 1] == '.' || (str[i + 1] >= '0' && str[i + 1] <= '9')) {//如果接下来是.或者数字,继续读
    				i++;
    				cout << str[i];
    			}
    		} else {//str[i]是符号 三种情况,1.只出栈不入栈情况:右括号,2.只入栈不出栈的情况:栈空或者栈顶优先级小于a[i]
    	//3.入栈+出栈:栈顶优先级>=a[i],不能是左括号
    			if (str[i] == ')') {//1.只出栈不入栈情况:右括号
    				while (!s.empty()&&s.top()!='(') {
    					cout << " " << s.top();
    					s.pop();
    				}
    				s.pop();//弹出左括号
    			} else if (s.size() == 0 || p[s.top()] < p[str[i]]) {//只入栈不出栈的情况:栈空或者栈顶优先级小于a[i]
    				s.push(str[i]);
    			} else {//3.入栈+出栈:栈顶优先级>=a[i],不能是左括号
    
    				while (!s.empty() && s.top() != '(' && p[s.top()] >= p[str[i]]) {
    					cout << " " << s.top();
    					s.pop();
    				}
    				s.push(str[i]);
    			}
    
    
    		}
    
    	}
    
    	//到最后,如果栈不空,弹出即可
    	while (!s.empty()) {
    		cout << " " << s.top();
    		s.pop();
    	}
    	cout << endl;
    	return 0;
    }
    
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,491
精华内容 5,796
关键字:

表达式求值