I want to know if there is a way to solve infix expressions in a single pass using 2 stacks? The stacks can be one for operator and the other for operands...
The standard way to solve by shunt-yard algorithm is to convert the infix expression to postfix(reverse polish) and then solve. I don't want to convert the expression first to postfix.
If the expression is like 2*3-(6+5)+8, how to solve?
リンクに記載されている方法は本当に良いです。
ソースを引用しましょう：
We will use two stacks:
Operand stack: to keep values (numbers) and
Operator stack: to keep operators (+, -, *, . and ^).
In the following, “process” means, (i) pop operand stack once (value1) (ii) pop operator stack once (operator) (iii) pop operand stack again (value2) (iv) compute value1 operator value2 (v) push the value obtained in operand stack.
Algorithm:
Until the end of the expression is reached, get one character and perform only one of the steps (a) through (f):
(a) If the character is an operand, push it onto the operand stack.
(b) If the character is an operator, and the operator stack is empty then push it onto the operator stack.
(c) If the character is an operator and the operator stack is not empty, and the character's precedence is greater than the precedence of the stack top of operator stack, then push the character onto the operator stack.
(d) If the character is "(", then push it onto operator stack.
(e) If the character is ")", then "process" as explained above until the corresponding "(" is encountered in operator stack. At this stage POP the operator stack and ignore "(."
(f) If cases (a), (b), (c), (d) and (e) do not apply, then process as explained above.
When there are no more input characters, keep processing until the operator stack becomes empty. The values left in the operand stack is the final result of the expression.
これが役立つことを願っています！