算法要求：
- 输入一个数学表达式(假定表达式输入格式合法)，计算表达式结果并输出。
- 数学表达式由单个数字和运算符“+”、“-”、“*”、“/”、“(、) ”构成，例如 2 + 3 * ( 4 + 5 ) - 6 / 4。
- 变量、输出采用整数，只舍不入。
图解算法思想：
1、图中1、2、3、4~~表示操作的前后顺序
2、图中橙色栈用来处理数字，黄色用来处理运算符。
3、本图实际上将中缀转后缀、后缀求值两步整合在一起
最后一步执行：取出‘-’，然后43-6=37，作为最后结果。
程序思想流程图：
代码如下：
【实验全部代码】 #include <iostream> #include <string> using namespace std; // 写一个栈的模板函数，因为下面需要用到 int 和 char 两种 stack 类型，且方法一样 template <class T> class Stack { private: T data[1001]; int size; // 同时承担 top 的作用 public: Stack() { size = 0; } ~Stack() { size = 0; } T pop() {//出栈 size--; return data[size]; } void push(T a) {//入栈 data[size++] = a; } T front() {//返回栈顶元素 return data[size - 1]; } void clear() {//清除栈中元素，非物理清除，仅逻辑清除 size = 0; } bool empty() {//判空 return (size == 0); } }; // 中序转后序函数 string inToSuffix(string s) { string result = ""; int size = s.size(); Stack<char> a; for (int i = 0; i < size; i++) { //对括号的处理 if (s[i] == '(') { a.push(s[i]); } else if (s[i] == ')') { if (!a.empty()) { char t = a.pop(); while (t != '(' && !a.empty()) { result.push_back(t); t = a.pop(); } } //加减乘除的处理 } else if (s[i] == '+' || s[i] == '-') { // 加减的等级是最低的 while (!a.empty()) { if (a.front() == '(') { break; } else { // 加减和乘除的处理方式一样，都是弹出 result.push_back(a.pop()); } } a.push(s[i]); } else if (s[i] == '*' || s[i] == '/') { while (!a.empty()) { if (a.front() == '(') { break; } else if (a.front() == '*' || a.front() == '/') { // 仅仅乘除被弹出，加减留在里面 result.push_back(a.pop()); } else break; // 如果遇到加减，则要直接 break，否则死循环 } a.push(s[i]); //数字的处理 } else if (s[i] >= '0' && s[i] <= '9') { result.push_back(s[i]); } else { cout << "存在非法输入" << endl; break; } } while (!a.empty()) { // 最后要把栈中所有东西一一输出 result.push_back(a.pop()); } return result; } int suffix_print(string s) { // 后缀表达式核心就在于运算顺序，所以中缀中的括号在后缀中已经转化为数字和运算的前后顺序 Stack<int> a; int size = s.size(); for (int i = 0; i < size; i++) { if (s[i] >= '0' && s[i] <= '9') a.push(s[i] - '0'); else { int s2 = a.pop(); int s1 = a.pop(); if (s[i] == '*') { a.push(s1 * s2); } else if (s[i] == '+') { a.push(s1 + s2); } else if (s[i] == '/') { a.push(s1 / s2); } else { a.push(s1 - s2); } } } return a.front(); } int main() { cout << "Input" << endl; string input; cin >> input; cout << "Output" << endl; string inpute1 = inToSuffix(input); cout << "=" << suffix_print(inpute1) << endl; cout << "End"; return 0; }
感悟与算法分析：
本题是实现计算器的制作。可以分为三个子问题：括号作用在数据结构中的实现、如何将中缀表达式化为后缀表达式、如何将后缀表达式的值计算出来 针对 问题一：对于一个表达式，我们采用栈的方式去存储。那么如何用栈来处理括号问题呢？
问题二：如何将中缀表达式转化为后缀表达式只要遵循下面这几个要求即可。
所以本问题可以利用多次的if判断语句，将问题分为这几种情况分别按照要求去处理 问题三：后缀表达式的求值也同样分为以下几个步骤来处理即可。
综上来说本题考察的主要是波兰表达式和逆波兰表达式的转化，以及逆波兰表达式的计算。而这些计算借助的数据结构就是栈。程序在书写的过程中最需要注意的就是if、elseif的分类处理。有一些类处理中需要用break来退出，否则会让程序进入死循环。其他一些注意点都在程序注释中标明。 |
仅供参考，一定不要直接复制！！！查重很严的！！！
