3.1 表达式求值（递归实现）

「爱情、让人受尽委屈。」 2022-05-09 00:36 169阅读 0赞

![70][]

![70 1][]

> 表达式可以是只有一个项组成，或者是多个项加减组成；
> 
> 项可以由一个因子组成，或者是多个因子乘除组成；
> 
> 因子可以由一个整数或者一个（表达式）组成。

![70 2][]

![70 3][]

![70 4][]

![70 5][]

![70 6][]

#include<iostream>
    #include<cstring>
    using namespace std;
    int term();
    int expr();
    int factor();
    
    int expr()
    {
    	int result = term();
    	bool more = true;	
    	while(more)
    	{
    		char c = cin.peek();
    		if(c == '+' || c == '-')
    		{
    			cin.get();
    			int value = term();
    			if(c == '+')
    				result += value;
    			else if(c == '-')
    				result -= value;
    		}
    		else more = false; 
    	}	
    	return result;
    }
    
    int term()
    {
    	int result = factor();
    	bool more = true;
    	while(more)
    	{
    		char c = cin.peek();
    		if(c == '*' || c == '/')
    		{
    			cin.get();
    			int value = factor();
    			if(c == '*')
    				result *= value;
    			else
    				result /= value;
    		}
    		else
    			more = false;
    	}
    	return result;
    }
    
    int factor()
    {
    	int result = 0;
    	char c = cin.peek();
    	if(c == '(')
    	{
    		cin.get();//去掉左括号 
    		result = expr();
    		cin.get();//去掉右括号 
    	}
    	else
    	{
    		while(isdigit(c))
    		{
    			result = result*10 + c - '0';
    			cin.get();
    			c = cin.peek() ;
    		}
    	} 
    	return result;
    }
    int main()
    {
    	cout << expr() << endl;
    	//cout << term() << endl;
    //	cout << factor() << endl; 
    	return 0;
    }

> 还有一种方法是通过栈来实现，后面更新~（因为递归就是通过栈实现的）

调试代码：

#include<iostream>
    #include<cstring>
    using namespace std;
    int term();
    int expr();
    int factor();
     
    int expr()
    {
    	cout<<"---expr---"<<endl;
    	int result = term();
    	cout<<"expr_first_result: "<<result<<endl;
    	bool more = true;	
    	while(more)
    	{
    		char c = cin.peek();
    		cout<<"expr_cin.peek(): "<<c<<endl;
    		if(c == '+' || c == '-')
    		{
    			cin.get();
    			int value = term();
    			if(c == '+')
    				result += value;
    			else if(c == '-')
    				result -= value;
    		}
    		else more = false; 
    	}
    	cout<<"expr_return_result: "<<result<<endl;	
    	cout<<"---expr---END"<<endl;
    	cout<<endl;
    	return result;
    }
     
    int term()
    {
    	cout<<"---term---"<<endl;
    	int result = factor();
    	cout<<"term_first_result: "<<result<<endl;
    	bool more = true;
    	while(more)
    	{
    		char c = cin.peek();
    		cout<<"term_cin.peek(): "<<c<<endl;
    		if(c == '*' || c == '/')
    		{
    			cin.get();
    			int value = factor();
    			if(c == '*')
    				result *= value;
    			else
    				result /= value;
    		}
    		else
    			more = false;
    	}
    	cout<<"term_return_result: "<<result<<endl;
    	cout<<"---term---END"<<endl;
    	cout<<endl;
    	return result;
    }
     
    int factor()
    {
    	cout<<"---factor---"<<endl;
    	int result = 0;
    	char c = cin.peek();
    	cout<<"factor_cin.peek(): "<<c<<endl;
    	if(c == '(')
    	{
    		cin.get();//去掉左括号 
    		result = expr();
    		cin.get();//去掉右括号 
    	}
    	else
    	{
    		while(isdigit(c))
    		{
    			result = result*10 + c - '0';
    			cin.get();
    			c = cin.peek() ;
    		}
    	} 
    	cout<<"factor_return_result: "<<result<<endl;	
    	cout<<"---factor---END"<<endl;
    	cout<<endl;
    	return result;
    }
    int main()
    {
    	freopen("in.txt","r",stdin); 
    	freopen("out.txt","w",stdout); 
    	cout << expr() << endl;
    	return 0;
    }

输入：

(2+3)+(5+7)+9/3

结果：

---expr---
    ---term---
    ---factor---
    factor_cin.peek(): (
    ---expr---
    ---term---
    ---factor---
    factor_cin.peek(): 2
    factor_return_result: 2
    ---factor---END
    
    term_first_result: 2
    term_cin.peek(): +
    term_return_result: 2
    ---term---END
    
    expr_first_result: 2
    expr_cin.peek(): +
    ---term---
    ---factor---
    factor_cin.peek(): 3
    factor_return_result: 3
    ---factor---END
    
    term_first_result: 3
    term_cin.peek(): )
    term_return_result: 3
    ---term---END
    
    expr_cin.peek(): )
    expr_return_result: 5
    ---expr---END
    
    factor_return_result: 5
    ---factor---END
    
    term_first_result: 5
    term_cin.peek(): +
    term_return_result: 5
    ---term---END
    
    expr_first_result: 5
    expr_cin.peek(): +
    ---term---
    ---factor---
    factor_cin.peek(): (
    ---expr---
    ---term---
    ---factor---
    factor_cin.peek(): 5
    factor_return_result: 5
    ---factor---END
    
    term_first_result: 5
    term_cin.peek(): +
    term_return_result: 5
    ---term---END
    
    expr_first_result: 5
    expr_cin.peek(): +
    ---term---
    ---factor---
    factor_cin.peek(): 7
    factor_return_result: 7
    ---factor---END
    
    term_first_result: 7
    term_cin.peek(): )
    term_return_result: 7
    ---term---END
    
    expr_cin.peek(): )
    expr_return_result: 12
    ---expr---END
    
    factor_return_result: 12
    ---factor---END
    
    term_first_result: 12
    term_cin.peek(): +
    term_return_result: 12
    ---term---END
    
    expr_cin.peek(): +
    ---term---
    ---factor---
    factor_cin.peek(): 9
    factor_return_result: 9
    ---factor---END
    
    term_first_result: 9
    term_cin.peek(): /
    ---factor---
    factor_cin.peek(): 3
    factor_return_result: 3
    ---factor---END
    
    term_cin.peek(): 
    term_return_result: 3
    ---term---END
    
    expr_cin.peek(): 
    expr_return_result: 20
    ---expr---END

[70]: /images/20220509/4e55d99b281e4226ac21735010764134.png
[70 1]: /images/20220509/d5ebccd26ccb4f00b7743d3d7cd8c245.png
[70 2]: /images/20220509/83411ca82d464438bceb7750abe4cfd5.png
[70 3]: /images/20220509/dca13bf6b3264c3f863a77b7bb66176b.png
[70 4]: /images/20220509/89c1a53faa9e44b294f1e64227e0dc09.png
[70 5]: /images/20220509/58d4d51972044d2aa331f36b2e427f59.png
[70 6]: /images/20220509/8b2af879d2134ce9aa6ac9cc5425dd4e.png