递归---表达式求值

￡神魔★判官ぃ 2023-06-25 06:29 83阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70]

# 解题思想： #

### 表达式是个递归的思想 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 2]  
**意思就是：输入一个表达式，该表达式包含了项，项右包含因子，因子是整数 或 表达式，若是整数则返回整数值，若是表达式则返回下一轮递归的值**

### 补充： ###

##### 表达式 == 项 + 加减运算符（+、- ） #####

##### 项 == 因子 + 乘除运算符（ \* 、/ ） #####

##### 因子 == 表达式 + 整数（int 型） #####

# 代码： #

#include <iostream>
    using namespace std;
    int factor(); //求一个因子的值
    int term(); //求一个项的值
    int expression(); //求一个表达式的值
    
    int main() //只能计算整数 
    { 
    	cout << expression() << endl;
    	return 0;
    }
    
    int expression() //求一个表达式的值
    { 
    	int result = term(); //求第一项的值
    	bool more = true; //查看是否只有一个表达式
    	while( more)
    	{ 
    		char op = cin.peek(); //看一个字符,不取走
    		if( op == '+' || op == '-' )
    		{ 
    			cin.get(); //从输入中取走一个字符
    			int value = term();
    			if( op == '+' ) result += value;
    			else result -= value;
    		}
    		else more = false;
    	}
    	return result;
    }
    
    int term() //求一个项的值
    { 
    	int result = factor(); //求第一个因子的值
    	while(true)
    	{ 
    		char op = cin.peek();
    		if( op == '*' || op == '/')
    		{ 
    		cin.get();
    		int value = factor();
    		if( op == '*') result *= value;
    		else result /= value;
    		}
    		else break;
    	}
    	return result;
    }
    
    int factor() //求一个因子的值
    { 
    	int result = 0;
    	char c = cin.peek();
    	if( c == '(')
    	{ 
    		cin.get();
    		result = expression();
    		cin.get();
    	}
    	else
    	{ 
    		while(isdigit(c))
    		{ 
    			result = 10 * result + c - '0';
    			cin.get();
    			c = cin.peek();
    		}
    	}
    	return result;
    }

cin.peek（）函数的作用是只看一个字符，不取走

**现在我们看一下此题中核心之一的代码：**

#include <iostream>
    using namespace std;
    int main()
    { 
    	int result = 0;
    	char c = cin.peek();
    	while(isdigit(c))
    	{ 
    		result = 10 * result + c - '0';
    		cin.get();
    		c = cin.peek();
    	}
    	cout<<result;
    	return 0;
    }

它的作用是能将输入的字符串中 连续的"数字" 变成 int 型数值，如：

input: 123123
    output: 123123

**它的作用和 atof（） 类似，但因为 atof（） 需要输入确定长度的数字字符，而本题中下一个字符是不确定的，下一个字符或许是数字字符、又或许是运算操作符，所以数字字符的长度不能确定，故不能使用 atof（）**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191227120917888.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191227121043494.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191227121119521.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70