编程语言栈单选难度 3真题改编 · 2024
18. 存在中缀表达式：(2*(3-4))*5，通过下面的代码将其转换为后缀表达式，则当扫描到字符4时，栈ops中所存元素为（）
/**
* 将中缀表达式转换为后缀表达式
* @param s 中缀表达式
* @return String字符串 后缀表达式
*/
private String postfix(String s){
// 后缀表达式
StringBuilder sb = new StringBuilder();
Stack<Character> ops = new Stack<>();
int i = 0;
while(i < s.length()){
char c = s.charAt(i++);
if (c == '(' || c == '+' || c == '-' || c == '*'){
// 加一个空格是为了将操作数之间隔开
sb.append(" ");
pushOP(sb,c,ops);
continue;
}
if (c == ')'){
// 弹出操作符直到(
while(ops.peek() != '('){
sb.append(ops.pop());
}
ops.pop();
continue;
}
sb.append(c);
}
// 弹出栈中元素
while(!ops.isEmpty()){
sb.append(ops.pop());
}
return sb.toString();
}
private void pushOP(StringBuilder sb,char op,Stack<Character> ops){
// 栈空，或者栈顶元素为(,操作符直接放入栈中
if (ops.isEmpty() || ops.peek() == '(' || op == '('){
ops.add(op);
return;
}
char c = ops.peek();
// 栈顶操作符的优先级低于当前操作符，直接压入栈中
if (c != '*' && op == '*'){
ops.add(op);
return;
}
// 否则，弹出栈顶元素，继续比较
c = ops.pop();
sb.append(c);
pushOP(sb,op,ops);
}
练习本题 ›