算法答疑---递归实现表达式求值
一、总结
一句话总结：表达式求值除了日常的栈做法，也可以用递归。
1、递归的核心是什么？
递推公式和边界条件
递推公式就是递归的逻辑，有时候不一定方便写出来
2、c++中int factor();形式的代码是做什么用的？
函数声明，c++中的函数声明是有带函数返回值的，也就是最前面那个int。
1 #include2 #include 3 using namespace std; 4 int term(); 5 int expr(); 6 int factor();
二、3.1 表达式求值（递归实现）
#include#include 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;}
还有一种方法是通过栈来实现，后面更新~
三、代码测试（代码的中间结果）
测试代码：
1 #include2 #include 3 using namespace std; 4 int term(); 5 int expr(); 6 int factor(); 7 8 int expr() 9 {10 cout<<"---expr---"<
in.txt
(2+3)+(5+7)+9/3
out.txt
1 ---expr--- 2 ---term--- 3 ---factor--- 4 factor_cin.peek(): ( 5 ---expr--- 6 ---term--- 7 ---factor--- 8 factor_cin.peek(): 2 9 factor_return_result: 2 10 ---factor---END 11 12 term_first_result: 2 13 term_cin.peek(): + 14 term_return_result: 2 15 ---term---END 16 17 expr_first_result: 2 18 expr_cin.peek(): + 19 ---term--- 20 ---factor--- 21 factor_cin.peek(): 3 22 factor_return_result: 3 23 ---factor---END 24 25 term_first_result: 3 26 term_cin.peek(): ) 27 term_return_result: 3 28 ---term---END 29 30 expr_cin.peek(): ) 31 expr_return_result: 5 32 ---expr---END 33 34 factor_return_result: 5 35 ---factor---END 36 37 term_first_result: 5 38 term_cin.peek(): + 39 term_return_result: 5 40 ---term---END 41 42 expr_first_result: 5 43 expr_cin.peek(): + 44 ---term--- 45 ---factor--- 46 factor_cin.peek(): ( 47 ---expr--- 48 ---term--- 49 ---factor--- 50 factor_cin.peek(): 5 51 factor_return_result: 5 52 ---factor---END 53 54 term_first_result: 5 55 term_cin.peek(): + 56 term_return_result: 5 57 ---term---END 58 59 expr_first_result: 5 60 expr_cin.peek(): + 61 ---term--- 62 ---factor--- 63 factor_cin.peek(): 7 64 factor_return_result: 7 65 ---factor---END 66 67 term_first_result: 7 68 term_cin.peek(): ) 69 term_return_result: 7 70 ---term---END 71 72 expr_cin.peek(): ) 73 expr_return_result: 12 74 ---expr---END 75 76 factor_return_result: 12 77 ---factor---END 78 79 term_first_result: 12 80 term_cin.peek(): + 81 term_return_result: 12 82 ---term---END 83 84 expr_cin.peek(): + 85 ---term--- 86 ---factor--- 87 factor_cin.peek(): 9 88 factor_return_result: 9 89 ---factor---END 90 91 term_first_result: 9 92 term_cin.peek(): / 93 ---factor--- 94 factor_cin.peek(): 3 95 factor_return_result: 3 96 ---factor---END 97 98 term_cin.peek(): 99 term_return_result: 3100 ---term---END101 102 expr_cin.peek(): 103 expr_return_result: 20104 ---expr---END105 106 20