逆波兰表达式_四则表达式

2023-10-22 06:48

文章标签 表达式波兰四则

本文主要是介绍逆波兰表达式_四则表达式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 逆波兰表达式实现的四则运算

在这里插入图片描述

2. 如何把中缀表达式转换为后缀表达式

这个就有点复杂了，待补充

hj50 四则运算

在这里插入图片描述
主要思路：
用两个栈来维护进行计算：
一个栈放运算符(“±*/(”), 一个栈放数字

// 如何判断'+'或'-'是加减还是正负？
// 用一个变量来判断：数字和运算符是交替出现的（括号的出现不会影响这种交替关系）#include <iostream>
#include <stack>
using namespace std;string mp = "+-*/)]}"; // 没有左括号void doCal(stack<double> &st, stack<char> &so)
{//数字栈中弹出的两个元素，谁减谁，这里顺序错了//double a=st.top();//第一次弹出的应该是要减去的值double b = st.top();st.pop();double a = st.top();st.pop();// 运算符char ch = so.top();so.pop();if (ch == '+')a = a + b;else if (ch == '-')a = a - b;else if (ch == '*')a = a * b;else if (ch == '/')a = a / b;st.push(a);return;
}bool cmp(char c1, char c2)
{if (c1 == '('){return false; // 因为所有左括号统一成(压入，遇到(,c2是什么运算符都继续压入栈，不是弹出栈顶，做运算}// 默认c1优先级<c2, 所以返回false, c2入栈else if ((c1 == '+' || c1 == '-') && (c2 == '*' || c2 == '/')){return false;}return true; // c2运算
}int main()
{string s;while (getline(cin, s)){stack<double> st; // 数字栈stack<char> so;   // 运算符栈so.push('(');s += ')';bool IsOp = false; //第一次一定是数字for (int i = 0; i < s.size(); i++){// 妈的这个括号，调bug半天if (s[i] == '(' || s[i] == '[' || s[i] == '{'){so.push('(');}else if (s[i] == ')' || s[i] == ']' || s[i] == '}'){while (so.top() != '('){doCal(st, so);}so.pop(); // 此时so.top()='(', 将‘(’出栈}// 遇到四则运算符：前面的两个判断已经把括号的情况去除了else if (IsOp){// 比较当前运算符和栈顶优先级,栈顶此刻只有两种可能：// 在（和运算符+ -*/中，若栈顶优先级高，运算while (cmp(so.top(), s[i])){doCal(st, so);}// 当前优先级高，入栈so.push(s[i]);IsOp = false; // 一个运算符结束后一定是数字}// 遇到运算符和数字，找到运算符数字长度，从字符串中截取，还原数字然后压入栈中// 只有 +33 与 -33才能进入这个循环else{int j = i; // i=0if (s[j] == '-' || s[j] == '+'){i++; // 运算符的索引位置为j, i=1定位数字的索引位置}// 这个是啥意思啊，看不懂：即没找到 +33，到33时都为mp.npos,所以i++=3while (mp.find(s[i]) == mp.npos) // 找不到就i++{i++; // i=3, 直到找到一个数字之后的运算符就退出}string t = s.substr(j, i - j); // substr(10, 12-10)st.push((double)stoi(t));      // stoi(string)=int, eg: stoi(-4)=-4i--;IsOp = true; // 数字之后一定是( 或者 四则运算符}}cout << st.top() << endl;}return 0;
}