中缀表达式转换为后缀表达式的规则 1.当遇到数字的话,直接输出 2.当遇到操作符,就要进行入栈或出栈操作 (1) 若栈为空,直接入栈 (2) 若栈不为空,判断一下优先级,若优先级 <= 栈顶元素,则栈顶元素出栈,直到遇到不能出栈的情况,把当前操作符入栈.特殊情况: 若栈顶是 ‘(’ 则这个操作符必须是’)‘才会出栈.比如现在栈顶是 ‘(’ ,而遇到了操作符 ‘+’,虽然’+’ 的优先级低于 ‘(’,但是任然要入栈.
优先级: ) : 0 加减: 1 乘除: 2 ( : 3 举例: 2+3*(7-4)+8/4 遇到2输出,遇到+入栈,遇到3输出,遇到*优先级大于+入栈,遇到(优先级大于*入栈,遇到7输出,遇到-号时 虽然’-'小于( 但是任然入栈,遇到4输出,遇到)优先级最低,栈内元素一直出栈,直到遇到( 现在栈里面只剩下+ *,这时候遇到操作符+ ,里面优先级小于等于它的都出,然后再把+放入栈,遇到8输出,遇到操作符/入栈,遇到4输出.最后只剩下栈里面的/ + 若栈不为空,就直接输出栈内所有元素
本题需要解决的问题: 1.当数是小数 会有小数点 . 2.当数为正负数时,前面会有**+ 、-** 正号要去掉 3.当出现多个括号时 4.当只出现一个数字,最后不应该有空格
import java.util.Scanner; import java.util.Stack; public class S7_13 { static char str[]; static String ans = ""; static Stack<Character> st; //栈 public static void main(String[] args) { Scanner sc = new Scanner(System.in); str = sc.next().toCharArray(); solve(); } static void solve() { st = new Stack<Character>(); for (int i = 0; i < str.length; i++) { if (str[i] >= '0' && str[i] <= '9') { //遇到数字 while (i < str.length && (str[i] >= '0' && str[i] <= '9' || str[i] == '.')) ans += str[i++]; if (i != str.length || !st.empty()) ans += " "; i--; //因为前面i++了 for 循环还是要加一次. 所以这里减一次 } else if (str[i] == '-') { //处理负号 if (i - 1 > 0 && (str[i - 1] == ')' || (str[i - 1] >= '0' && str[i - 1] <= '9') )) { f(i); // 当做操作符 } else { ans += str[i];//当作数前面的负号 } } else if (str[i] == '+') { if (i - 1 >= 0 && (str[i - 1] == ')' || (str[i - 1] >= '0' && str[i - 1] <= '9') )) { f(i);//当做操作符 } } else { f(i); // 遇到 * / ( ) 直接当作操作符 } } while (!st.empty()) { //打印栈里面没有弹出完的操作符 ans += st.pop() + " "; } if (ans.charAt(ans.length() - 1) == ' ') { System.out.println(ans.substring(0,ans.length() - 1)); } else { System.out.println(ans); } } //将i位置的字符当作操作符处理 static void f(int i ) { if (st.empty()) { //栈为空 不用判断 操作符的优先级 st.add(str[i]); } else { int a = getPri(st.peek()); // 获得优先级 int b = getPri(str[i]); if (b > a) { st.add(str[i]); } else { if (str[i] == ')') { while (a >= b) { if (st.peek() != '(') { ans += st.pop(); if (!st.empty() || i < str.length ) ans += " "; } else { st.pop(); break; //只弹一个出来 . 一个右括号只匹配一个 } if (st.empty()) break; a = getPri(st.peek()); } } else { while (a >= b && a != 3) { ans += st.pop(); if (!st.empty() || i < str.length) ans += " "; if (st.empty()) break; a = getPri(st.peek()); } st.add(str[i]); } } } } static int getPri(char c) { // ):0 +,-:1 *,/:2 (:3 if (c == ')') return 0; if (c == '+' || c == '-') return 1; if (c == '*' || c == '/') return 2; if (c == '(') return 3; return -1; } } #include<iostream> #include<string> #include<stack> using namespace std; int main(){ int len; string str; char c; stack<char>st; cin>>str; len=str.length(); int x; for(int i=0;i<len;i++){ if(str[i]=='('){ st.push(str[i]); continue; } if(str[i]>='0'&&str[i]<='9'){ if(i-1>=0&&str[i-1]=='-'){ cout<<'-'; } if(i-1>=0&&str[i-1]=='+'){ continue; } while(i<len&&((str[i]>='0'&&str[i]<='9')||str[i]=='.')){ cout<<str[i]; i++; } x=i; break; } } for(int i=x;i<len;i++){ if(str[i]>='0'&&str[i]<='9'){ cout<<' '; if(i-1>=0&&str[i-1]=='-'&&i-2>=0&&(str[i-2]=='('||str[i-2]=='+'||str[i-2]=='-'||str[i-2]=='*'||str[i-2]=='/')){ cout<<'-'; } while(i<len&&((str[i]>='0'&&str[i]<='9')||str[i]=='.')){ cout<<str[i]; i++; } i--; continue; } if(str[i]=='('){ st.push('('); continue; } if(str[i]==')'){ while(!st.empty()&&(c=st.top())!='('){ cout<<' '<<c; st.pop(); } st.pop(); continue; } if(str[i]=='+'||str[i]=='-'){ if(i-1>=0&&(str[i]=='-'||str[i]=='+')&&(str[i-1]=='+'||str[i-1]=='-'||str[i-1]=='*'||str[i-1]=='/'||str[i-1]=='(')){ continue; } while(!st.empty()&&(st.top()!='(')){ cout<<' '<<st.top(); st.pop(); } st.push(str[i]); continue; } if(str[i]=='*'||str[i]=='/'){ while(!st.empty()&&(st.top()=='*'||st.top()=='/')){ cout<<' '<<st.top(); st.pop(); } st.push(str[i]); } } while(!st.empty()){ cout<<' '<<st.top(); st.pop(); } }