|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
//后缀表达式，又称为逆波兰表达式
|
|
|
#pragma region C++实现的中缀表达式转后缀表达式
|
|
|
const int MAXSIZE = 256;
|
|
|
|
|
|
/*
|
|
|
将中缀表达式转换为后缀表达式
|
|
|
参数:infix 指向中缀表达式，以回车键即\n结尾。
|
|
|
postfix 指向后缀表达式临时缓冲区，用来存放转换后的结果。
|
|
|
附转换规则：从左到右遍历中缀表达式的每个数字和符号，若是数字则直接保存在postfix数组中；若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级不大于栈顶符号，则栈顶元素依次出栈并输出，直到遇到左括号或者栈空时，才将刚才的那个符号入栈。
|
|
|
*/
|
|
|
int InfixToPostfix(char *infix, char *postfix) {
|
|
|
stack<char> s;
|
|
|
char c, e;
|
|
|
int j = 0, i = 0;
|
|
|
c = *(infix + i); //取出中缀表达式中的第一个字符
|
|
|
i++;
|
|
|
while ('\n' != c) //遇到换行符，表示转换结束
|
|
|
{
|
|
|
while (c >= '0' && c <= '9') //先判断一下取出的字符是否是数字，如果是数字的话，则直接存入postfix数组
|
|
|
{
|
|
|
postfix[j++] = c;
|
|
|
c = *(infix + i);
|
|
|
i++;
|
|
|
if (c < '0' || c > '9') //如果不是数字，则在后面添加空格，以便区分各个符号
|
|
|
{
|
|
|
postfix[j++] = ' ';
|
|
|
}
|
|
|
}
|
|
|
if (')' == c) //不是数字，则判断是否为右括号。[括号的优先级最高，所以，如果是右括号的话，就得先进行括号里的各种运算]
|
|
|
{
|
|
|
e = s.top();
|
|
|
s.pop();
|
|
|
while ('(' != e) //直到遇到左括号为止
|
|
|
{
|
|
|
postfix[j++] = e;
|
|
|
postfix[j++] = ' ';
|
|
|
e = s.top();
|
|
|
s.pop();
|
|
|
}
|
|
|
} else if ('+' == c || '-' == c) //如果是加减号,因为他俩的优先级最低了，所以此时先将栈里的所有符号出栈后(除非遇到左括号)，再把此符号入栈
|
|
|
{
|
|
|
if (!(s.size())) //如果是空栈，则直接将加减号入栈
|
|
|
{
|
|
|
s.push(c);
|
|
|
} else//如果不是空栈，首先将所有优先级大于加减的出栈，然后再把加减号入栈
|
|
|
{
|
|
|
do {
|
|
|
e = s.top();
|
|
|
s.pop();
|
|
|
if ('(' == e) {
|
|
|
s.push(e);
|
|
|
} else {
|
|
|
postfix[j++] = e;
|
|
|
postfix[j++] = ' ';
|
|
|
}
|
|
|
} while (s.size() && '(' != e); //将栈里的所有符号出栈(除非遇到左括号)
|
|
|
s.push(c); //最后将新来的加减号再入栈
|
|
|
}
|
|
|
} else if ('*' == c || '/' == c || '(' == c) //如果是乘除号或左括号，因为他们的优先级高，所以直接入栈。
|
|
|
{
|
|
|
s.push(c);
|
|
|
} else if ('\n' == c) //判断一下，所有符号是否都已转换完成
|
|
|
{
|
|
|
break;
|
|
|
} else //能走到这个else的，都是我不认识的符号了
|
|
|
{
|
|
|
// printf("\nError:input error,the character %d cann't recognize!\n",c);
|
|
|
return -1;
|
|
|
}
|
|
|
c = *(infix + i); //取出下一个字符进行转换
|
|
|
i++;
|
|
|
}
|
|
|
while (s.size()) //转换完成后，栈里可能还有没出栈的运算符号
|
|
|
{
|
|
|
e = s.top();
|
|
|
s.pop();
|
|
|
postfix[j++] = e;
|
|
|
postfix[j++] = ' ';
|
|
|
}
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
计算后缀表达式的结果
|
|
|
参数：arr使用空格分隔的后缀表达式字符串。例：arr="31 5 + "
|
|
|
result 保存计算完毕后的结果
|
|
|
注：如何利用栈来计算后缀表达式的结果：依次取出后缀表达式中的符号进行比较，如果是数字，则直接入栈；如果是符号，则出栈两次，弹出两个要计算的因数，进行计算，之后再将计算结果入栈。知道后缀表达式中所有符号都已比较完毕。
|
|
|
*/
|
|
|
double Calculate(char *arr) {
|
|
|
double d, e, f; //d,e 存放两个因数。f存放d,e计算后的结果.
|
|
|
stack<double> s;
|
|
|
char *op; //存放后缀表达式中的每个因数或运算符
|
|
|
char *buf = arr; //声明bufhe saveptr两个变量，是strtok_r函数的需要。
|
|
|
while ((op = strtok(buf, " ")) != NULL) //利用strtok_r函数分隔字符串
|
|
|
{
|
|
|
buf = NULL;
|
|
|
switch (op[0]) {
|
|
|
case '+':
|
|
|
d = s.top();
|
|
|
s.pop();
|
|
|
e = s.top();
|
|
|
s.pop();
|
|
|
f = d + e;
|
|
|
s.push(f);
|
|
|
break;
|
|
|
case '-':
|
|
|
d = s.top();
|
|
|
s.pop();
|
|
|
e = s.top();
|
|
|
s.pop();
|
|
|
f = e - d;
|
|
|
s.push(f);
|
|
|
break;
|
|
|
case '*':
|
|
|
d = s.top();
|
|
|
s.pop();
|
|
|
e = s.top();
|
|
|
s.pop();
|
|
|
f = d * e;
|
|
|
s.push(f);
|
|
|
break;
|
|
|
case '/':
|
|
|
d = s.top();
|
|
|
s.pop();
|
|
|
e = s.top();
|
|
|
s.pop();
|
|
|
f = e / d;
|
|
|
s.push(f);
|
|
|
break;
|
|
|
default:
|
|
|
d = atof(op); //不是运算符，就肯定是因数了。所以，用atof函数，将字符串转换为double类型
|
|
|
s.push(d);
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
double result = s.top();
|
|
|
s.pop();
|
|
|
return result;
|
|
|
}
|
|
|
|
|
|
#pragma endregion C++实现的中缀表达式转后缀表达式
|
|
|
|
|
|
// 示意图：
|
|
|
// https://www.cnblogs.com/lulipro/p/7450886.html
|
|
|
|
|
|
char in[MAXSIZE] = {0};
|
|
|
char postfix[MAXSIZE] = {'\0'};
|
|
|
|
|
|
int main() {
|
|
|
//给的测试用例，后缀表达式的运算符号居然是贴在一起的，还需要手动将其分离开就行了。
|
|
|
string s = "";
|
|
|
int pos = 0;
|
|
|
getline(cin, s);
|
|
|
for (int i = 0; i < s.size(); ++i) {
|
|
|
if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
|
|
|
postfix[pos] = s[i];
|
|
|
postfix[pos + 1] = ' ';
|
|
|
pos += 2;
|
|
|
} else {
|
|
|
postfix[pos] = s[i];
|
|
|
pos++;
|
|
|
}
|
|
|
}
|
|
|
//输出后缀表达式
|
|
|
puts(postfix);
|
|
|
//计算后缀表达式
|
|
|
cout << Calculate(postfix);
|
|
|
return 0;
|
|
|
}
|
