本文参考自北大郭炜老师在中国大学mooc的算法基础课程。
输入为四则运算表达式，仅由整数、 +、－、 *、 / 、 (、 )组成，没有空格，要求求其值。假设运算符结果都是整数。 "/"结果也是整数 。
中缀表达式递归的定义：
表达式：由单独的“项”或“项”与“＋”或“－”运算符连接形成；
项：由单独的“因子”或“因子”与乘号或除号连接而成；
因子：可以是单独的整数，也可以是用括号括起来的“表达式”。
1 #include <iostream>
2 using namespace std;
3 int factor_value();//读入一个因子并返回其值
4 int term_value(); //读入一个项并返回其值
5 int expression_value();//读取一个表达式并返回其值
6 int main()
7 {
8 cout << expression_value() << endl;
9 return 0;
10 }
11 int expression_value() //求一个表达式的值
12 {
13 int result = term_value(); //求第一项的值
14 bool more = true;
15 while( more)
16 {
17 char op = cin.peek(); //看输入流的下一个字符,不取走
18 if( op == '+' || op == '-' )
19 {
20 cin.get(); //从输入中取走一个字符
21 int value = term_value();
22 if( op == '+' ) result += value;
23 else result -= value;
24 }
25 else more = false;
26 }
27 return result;
28 }
29
30 int term_value() //求一个项的值
31 {
32 int result = factor_value(); //求第一个因子的值
33 while(true)
34 {
35 char op = cin.peek();//看输入流的下一个字符,不取走
36 if( op == '*' || op == '/')
37 {
38 cin.get();//从输入中取走一个字符
39 int value = factor_value();
40 if( op == '*') result *= value;
41 else result /= value;
42 }
43 else break;
44 }
45 return result;
46 }
47
48 int factor_value() //求一个因子的值
49 {
50 int result = 0;
51 char c = cin.peek();//看输入流的下一个字符,不取走
52 if( c == '(')
53 {
54 cin.get();//从输入中取走一个字符。这里是取走左括号
55 result = expression_value();
56 cin.get();//从输入中取走一个字符。这里是取走右括号
57 }
58 else
59 {
60 while(isdigit(c)) //读取一个整数
61 {
62 result = 10 * result + c - '0';
63 cin.get();
64 c = cin.peek();
65 }
66 }
67 return result;
68 }
类似题目：布尔表达式